TY  - EJOU
AU  - Mohamed, Basma 
AU  - Mohaisen, Linda 
AU  - Amin, Mohamed 

TI  - Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization
T2  - Intelligent Automation \& Soft Computing

PY  - 2023
VL  - 36
IS  - 2
SN  - 2326-005X

AB  - In this paper, we consider the NP-hard problem of finding the minimum connected resolving set of graphs. A vertex set <i>B</i> of a connected graph <i>G</i> resolves <i>G</i> if every vertex of <i>G</i> is uniquely identified by its vector of distances to the vertices in <i>B</i>. A resolving set <i>B</i> of <i>G</i> is connected if the subgraph  induced by <i>B</i> is a nontrivial connected subgraph of <i>G</i>. The cardinality of the minimal resolving set is the metric dimension of <i>G</i> and the cardinality of minimum connected resolving set is the connected metric dimension of <i>G</i>. 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 <i>S</i>-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 <i>V</i>\<i>B</i> is added to <i>B</i> 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.
KW  - Connected resolving set; binary optimization; harris hawks algorithm

DO  - 10.32604/iasc.2023.032930