Open Access iconOpen Access

ARTICLE

crossmark

Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization

Basma Mohamed1,*, Linda Mohaisen2, Mohamed Amin1

1 Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin Elkom, 32511, Egypt
2 Faculty of Computer and Information Technology, King Abdulaziz University, Jeddah, 21589, Saudi Arabia

* Corresponding Author: Basma Mohamed. Email: email

Intelligent Automation & Soft Computing 2023, 36(2), 2349-2361. https://doi.org/10.32604/iasc.2023.032930

Abstract

In this paper, we consider the NP-hard problem of finding the minimum connected 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. A resolving set B of G is connected if the subgraph induced by B is a nontrivial connected subgraph of G. The cardinality of the minimal resolving set is the metric dimension of G and the cardinality of minimum connected resolving set is the connected metric dimension of G. The problem is solved heuristically by a binary version of an enhanced Harris Hawk Optimization (BEHHO) algorithm. This is the first attempt to determine the connected resolving set heuristically. BEHHO combines classical HHO with opposition-based learning, chaotic local search and is equipped with an S-shaped transfer function to convert the continuous variable into a binary one. The hawks of BEHHO are binary encoded and are used to represent which one of the vertices of a graph belongs to the connected resolving set. The feasibility is enforced by repairing hawks such that an additional node selected from V\B is added to B up to obtain the connected resolving set. The proposed BEHHO algorithm is compared to binary Harris Hawk Optimization (BHHO), binary opposition-based learning Harris Hawk Optimization (BOHHO), binary chaotic local search Harris Hawk Optimization (BCHHO) algorithms. Computational results confirm the superiority of the BEHHO for determining connected metric dimension.

Keywords


Cite This Article

B. Mohamed, L. Mohaisen and M. Amin, "Computing connected resolvability of graphs using binary enhanced harris hawks optimization," Intelligent Automation & Soft Computing, vol. 36, no.2, pp. 2349–2361, 2023.



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 726

    View

  • 326

    Download

  • 0

    Like

Share Link