A HYBRID OPTIMIZATION ALGORITHMS FOR SOLVING METRIC DIMENSION PROBLEM

摘要

In this paper, we consider the NP-hard problem of finding the minimum resolving set of graphs. A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The cardinality of the minimal resolving set is the metric dimension of G. The metric dimension appears in various fields such as network discovery and verification, robot navigation, combinatorial optimization and pharmaceutical chemistry, etc. In this study, we introduce a hybrid approach (WCA_WOA) for computing the metric dimension of graphs that combines the water cycle algorithm and a whale optimisation algorithm. The WOA algorithm hybridises the WCA in order to obtain the optimal result and manage the optimization process. The results of the experiments show that the WCA_WOA hybrid algorithm outperforms the WCA, WOA, and particle swarm optimization methods