Open Access

ARTICLE

Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization

Basma Mohamed^1,*, Linda Mohaisen², Mohamed Amin¹

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:

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

Received 02 June 2022; Accepted 22 September 2022; Issue published 05 January 2023

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

---