# Binary Equilibrium Optimization Algorithm for Computing Connected Domination Metric Dimension Problem

Authors: Basma Mohamed; Linda Mohaisen; Mohamed Amin
Journal: Scientific Programming
 (2022)

---

## Abstract

We consider, in this paper, the NP-hard problem of finding the minimum connected domination metric dimension of graphs. A vertex setB of a connected graph G = (V, E) 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 B¯ induced by B is a nontrivial connected subgraph of G. A resolving set is dominating if every vertex of G that does not belong to B is a neighbor to some vertices in B. The cardinality of the smallest resolving set of G, the cardinality of the minimal connected resolving set, and the cardinality of the minimal connected domination resolving set are the metric dimension of G, connected metric dimension of G, and connected domination metric dimension of G, respectively. We present the first attempt to compute heuristically the minimum connected dominant resolving set of graphs by a binary version of the equilibrium optimization algorithm (BEOA). The particles of BEOA are binary-encoded and used to represent which one of the vertices of the graph belongs to the connected domination resolving set. The feasibility is enforced by repairing particles such that an additional vertex generated from vertices of G is added to B, and this repairing process is iterated until B becomes the connected domination resolving set. The proposed BEOA is tested using graph results that are computed theoretically and compared to competitive algorithms. Computational results and their analysis show that BEOA outperforms the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer (BPSO), the binary Whale Optimizer (BWO), the binary Slime Mould Optimizer (BSMO), the binary Grasshopper Optimizer (BGO), the binary Artificial Ecosystem Optimizer (BAEO), and the binary Elephant Herding Optimizer (BEHO).


---

## Body

## 1. Introduction

Recently, connected domination metric dimension of graphs is introduced in [1]. Metric dimension has several applications in robot navigation [2, 3], network discovery and verification [4], application to wireless sensor network localization [5], pattern recognition, image processing [6], combinatorial optimization [7], and applications to pharmaceutical chemistry [8]. Domination theory is applied in wireless communication networks [9], electrical networks [10], and chemical structures [11]. The connected domination set with smallest cardinality is a natural candidate to be used for the information exchange in any kind of network. The utilization of connected domination sets of graphs for defining virtual backbone architecture in ad hoc wireless networks has been explored in [12–15].


## 2. Problem Description

LetG = (V, E) be a connected graph, and let d(u,v) be the shortest path between two vertices u,v∈V(G). An ordered vertex set B = {x1,x2,...,xk}⊆ V(G) is a resolving set of G if the representation(1)rv|B=dv,x1,dv,x2,…,dv,xk,is unique for every v∈V(G). A resolving set B is a dominating set of G if every vertex of V\B has at least one neighbor that belongs to B. A dominating resolving set B is connected if the subgraph B¯ induced by B is a nontrivial connected subgraph of G. Let Card (X) denote the cardinality of a set X. The metric dimension of G, denoted as dim(G), the domination metric dimension of G, denoted as Ddim(G), and the connected domination metric dimension of G, denoted as γcr (G), are defined as(2)dimG=minCardB:BisaresolvingsetofG,dimG=minCardB:BisadominationresolvingsetofG,YcrG=minCardB:BisaconnecteddominatingresolvingsetofG.cr.Example 1.
For the fan graphF7 given in Figure 1, the set B = v1,v3,v5 is a minimal resolving set, so dim(F7) = 3. B is also a minimal domination resolving set since every vertex of V\B has at least one neighbor that belongs to B, e.g., v2 is adjacent to v1 and v3, v4is adjacent to v1, v3 and v5, v6is adjacent to v1, v5 and v7, and v7is adjacent to v1, v6,soDdimF7 = 3. However, B is not connected domination resolving set of F7 since v4 is not connected to vertices in B. On the other hand, the set B = v1,v3,v4,v5 is a minimal connected domination resolving set of F7, so γcr (F7) = 4.
The connected domination metric dimension problem combines three components: connectedness, domination, and metric dimension of graphs. The problem of finding the metric dimension of a graphG is described in terms of an integer programming problem [8]. Let D = [dij] be the distance matrix of G, dij = dvi,vj for 1 ≤ i, j ≤ n. For xi ∈ {0, 1}, 1 ≤ i ≤ n, the function F is defined by(3)Fx1,x2.,……,xn=x1+x2+···+xn.Minimizing F subject to the n/2 constraints(4)di1−dj1x1+di2−dj2x2+…………+din−djnxn>0for1≤i<j≤n,is equivalent to finding a basis in the sense that if x1′,x2′,…,xn′ is a set of values for which F attains its minimum, then B = vi,xi′=1is a basis for G and conversely, if B = vi1,vi2,…,vinis a basis for G and if we define(5)xs′=1,ifs=ijforsomej1≤j≤k0,otherwise,then F( x1′,x2′,…,xn′) is a minimum subject to the given constraints.
The dominating set problem is NP-complete [16], and the metric dimension problem is NP-complete [17]. Consequently, the connected domination metric dimension γcr (G) is a typical NP-complete problem that involves determining if γcr (G) ≤ K for a given graph G and input K.
The rest of the paper is organized as follows: Section3 gives a literature review. Section 4 introduces the Equilibrium Optimization Algorithm (EOA). Section 5 gives the BEOA for computing the connected domination metric dimension. Section 7 reports computational results. Finally, Section 7 provides the conclusion and future work.Figure 1
Fan graphF7.


## 3. Literature Review

Metric dimension, domination metric dimension, and connected domination metric dimension of graphs are determined theoretically for several graphs in the literature. A short overview of the main recently determined theoretically metric dimension results [17–23] is given hereafter. The metric dimensions of the total graph of path powers three and four are determined theoretically in [18], symmetrical planar pyramid graph and reflection symmetrical planar pyramid graph in [19], m-level gear graph and generalized gear graph in [17], kayak paddles graph and cycles with chord in [20], circulant graphs in [21], generalized families of Toeplitz graphs in [22], and windmill graphs in [23].The connected metric dimension are determined theoretically in [24, 25]. Cycle graph, wheel graph, star graph, complete graph, and path graph are determined in [24] and Petersen graph in [25].The dominant metric dimension are determined theoretically in [26, 27]. Path graph, cycle graph, star graph, complete graph, and complete bipartite graph are determined in [26], the corona product graph of G and H is investigated whenever H is a path graph, and the cycle graph, complete bipartite graph, complete graph, and star graph Sn are determined in [27].The connected domination metric dimensions of complete graph, path graph, and cycle graph are determined theoretically in [1].On the other hand, only a few algorithms have been proposed to compute heuristically the metric dimension problem [28–30]. In [28], a genetic algorithm has been developed for computing the metric dimension of many classes of graph instances including pseudo-Boolean, crew scheduling and graph coloring. The binary representation, frozen genes mutation, a limited number of different individuals with the same objective value, and the caching technique were all applied. Infeasible individuals are changed by the addition of the required nodes in order to become feasible. In [29], PSO is adapted for determining the metric dimension where a real valued vector of vertices is converted to binary valued vector by a linear function and infeasible particles are repaired by adding some vertices until the particles become feasible. The PSO is tested by computing the metric dimension of hypercube graphs. A variable neighborhood search approach has been proposed for solving metric dimension and minimal doubly resolving set problems in order to improve the existing upper bounds in [30]. The variable neighborhood search approach is based on a decomposition of the metric dimension problem and the minimal doubly resolving set problem into a sequence of subproblems with an auxiliary objective function. In addition, for both problems, the corresponding new integer linear programming formulations are proposed.Here, the operations of the EOA are encoded and adapted to solve the connected domination metric dimension problem. The proposed BEOA is tested using graph results that are computed theoretically and is compared to competitive algorithms.


## 4. Equilibrium Optimization Algorithm (EOA)

The original EOA is a physics-based metaheuristic algorithm for handling continuous optimization problems in [31]. The EOA is a recently proposed metaheuristic algorithm that uses an equilibrium pool and candidates to update particles. The EOA is based on the analytic solution procedure for a well-mixed dynamic mass balance on a control volume. The EOA avoids falling into the local optimum in addition to having great exploitation and exploration capabilities. These benefits of EOA are made possible by the concept of generation rate.The mass balance equation is solved analytically, yielding the following results:(6)C=Ceq+C0+Ceq.F+GλV1−F,where V is considered to be 1 as the volume unit.The EOA generates an equilibrium pool with four candidates and another averaged one:(7)Ceqs,pool=Ceqs0,Ceqs1,Ceqs2,Ceqs3,Cave,(8)Cave=Ceqs0+Ceqs1+Ceqs2+Ceqs34.The fitness values of the candidates in the equilibrium pool should satisfy the following rules for a given problem represented byf:(9)fCeqs0≤fCeqs1≤fCeqs2≤fCeqs3.EOA uses the same initializing and iterating techniques as other bioinspired algorithms when solving problems, whether they are stated as benchmarks or come from real engineering work. While iterating, the EOA continues its domain exploration and exploitation operations. To improve performance, there are numerous specific operations in constructing the EOA.


### 4.1. The Initialization Procedure

Assuming that the presented problems are constrained by a symmetric or asymmetric domain with [lb,ub], the candidates of the swarms are uniformly distributed across the domain. To achieve this, the pseudo-random random numberr1 is introduced: (10)Ci=lb+ub−lb.r1.The position vector for theith candidate is Ci.


### 4.2. The Random Chosen Candidate

The positions of the candidates for the following iteration would be significant to three phases during the iterations, as equated in equation (6). Ceq is a randomly selected candidate from the swimming pool constructing with equation (7) for the first phase.


### 4.3. The Exponential Parameter

There is an exponential parameterF for the second part of equation (6), which is determined as follows:(11)F=a1signr2−0.5e−λt−1,where a1 is a constant variable that controls exploring capabilities as well as a parameter splitting the exploring and exploiting procedure. The higher the value of a1, the higher the probability for candidates to carry on exploration, and the smaller the probability for candidates to carry on exploitation. For experience and convenience, a1 = 2.r2 is another random number with the interval of [0, 1], and t is a parameter formulated to be related to the iteration times.(12)t=1−itermaxItera2iter/maxIter,where iter denotes the current iteration number, and maxIter denotes the maximum iteration number restricted at the start.


### 4.4. The Generation Rate Parameter

The wordG stands for the generation rate parameter, which improves the exploiting capability of candidates. The rate of generation is proportional to the exponential parameter, which is given as follows:(13)G=GoF,(14)Go=GCP⋅Ceq−λC,(15)GCP=0.5,r2≥GP,0,r2≥GP.GP stands for generation probability. GP is set to be 0.5 to achieve better results in balancing the probability between exploration and exploitation. Updating rule of EO will be as follows:(16)C=Ceq+C−Ceq.F+GƛV1−F,where F is defined in equation (11) and V is considered as unit.


## 4.1. The Initialization Procedure

Assuming that the presented problems are constrained by a symmetric or asymmetric domain with [lb,ub], the candidates of the swarms are uniformly distributed across the domain. To achieve this, the pseudo-random random numberr1 is introduced: (10)Ci=lb+ub−lb.r1.The position vector for theith candidate is Ci.


## 4.2. The Random Chosen Candidate

The positions of the candidates for the following iteration would be significant to three phases during the iterations, as equated in equation (6). Ceq is a randomly selected candidate from the swimming pool constructing with equation (7) for the first phase.


## 4.3. The Exponential Parameter

There is an exponential parameterF for the second part of equation (6), which is determined as follows:(11)F=a1signr2−0.5e−λt−1,where a1 is a constant variable that controls exploring capabilities as well as a parameter splitting the exploring and exploiting procedure. The higher the value of a1, the higher the probability for candidates to carry on exploration, and the smaller the probability for candidates to carry on exploitation. For experience and convenience, a1 = 2.r2 is another random number with the interval of [0, 1], and t is a parameter formulated to be related to the iteration times.(12)t=1−itermaxItera2iter/maxIter,where iter denotes the current iteration number, and maxIter denotes the maximum iteration number restricted at the start.


## 4.4. The Generation Rate Parameter

The wordG stands for the generation rate parameter, which improves the exploiting capability of candidates. The rate of generation is proportional to the exponential parameter, which is given as follows:(13)G=GoF,(14)Go=GCP⋅Ceq−λC,(15)GCP=0.5,r2≥GP,0,r2≥GP.GP stands for generation probability. GP is set to be 0.5 to achieve better results in balancing the probability between exploration and exploitation. Updating rule of EO will be as follows:(16)C=Ceq+C−Ceq.F+GƛV1−F,where F is defined in equation (11) and V is considered as unit.


## 5. Binary EOA for the Connected Dominated Metric Dimension Problem

[31]. The high performance of EOA is mainly derived from its extensive design in balancing exploration and exploitation abilities. This advantage makes a binary version of the algorithm that uses binary encoding, which can be adapted to solve the connected domination metric dimension problem. In the continuous version of EOA, particles can move around the search space using position vectors within the continuous real domain. We convert EOA to binary values by applying an S-shaped transfer function to transform the continuous variable into a binary one. In discrete binary search space, position updates require switching between 0 and 1.The following equation is used in the initialization step.(17)Cbinaryij=1,rand≥0.5,0,else.The rand() has uniform distribution, with a value of [0.0, 1.0], andCbinaryij is binary valued position vector. To convert continuous values to binary ones, a transfer function is used. The sigmoid function (S) is used in this study as follows:(18)S=11+e−10xd,where xd indicates the continuous-valued position at dimension d and S is the function output. To generate a binary value, apply the following equation:(19)Cbinaryij=1,rand<S,0,otherwise.The proposed algorithm deals with the connected domination resolving set problem as an optimization problem where it searches for the best solution, so each particle can be represented as a one-dimensional vectorCbinaryij = {Ci1, Ci2, Ci3, …, Cij}, and Cbinaryij is a binary valued position vector if j-th element of the vector has a value of 1; it means that vertex j belongs to B. If every v ∈V(G) has a unique representation rv|B, then B is a connected domination resolving set. The value of a binary valued position vector is produced by computing the value of the S-shaped transfer function. In the BEO algorithm, when a particle is not feasible as a connected domination resolving set, that particle is repaired by adding a vertex from V\B. This repair is applied until that particle becomes connected domination resolving set.The algorithm represents each solution (individual) in the population as a string of binary in which 1 means that the connected domination resolving set will be chosen, and then the corresponding value will be “1,” and if the connected domination resolving set is not selected, then the corresponding value will be “0.”The proposed BEO algorithm is displayed in Algorithm1.Algorithm 1: Pseudo-BEOA.
Initialize the particle’s populationsi = 1,…,nAssign equilibrium candidates’ fitness a large numberAssign free parametersa1 = 2; a2 = 1; GP = 0.5;While Iter < Max_iterFori = 1: number of particles (n)Calculate fitness ofith particleIf (Ci) < (Ceq0)ReplaceCeq0with Ci and fit (Ceq0) with (Ci)Convert eachCiinto binary using S-shaped transfer function in Cbinary ijCalculate the fitness of eachCbinary ijUpdate new position of the candidate using (16)Else if (Ci) > (Ceq0 ) & (Ci)) < (Ceq1)ReplaceCeq1 with Ci and fit (Ceq1) with (Ci)Convert eachCiinto binary using S-shaped transfer function in Cbinary ijCalculate the fitness of eachCbinary ijUpdate new position of the candidate using (16)Else if (Ci) > ((Ceq0 ) & (Ci) > (Ceq1) & (Ci) < (Ceq2)ReplaceCeq2 with Ci and fit (Ceq2) with (Ci)Convert eachCiinto binary using S-shaped transfer function in CbinaryijCalculate the fitness of eachCbinaryijUpdate new position of the candidate using (16)Else if (Ci) > (Ceq0) & (Ci) > (Ceq1) & (Ci) > (Ceq2) & (Ci)) < (Ceq3)ReplaceCeq3 with Ci and fit (Ceq3 ) with (Ci)Convert eachCiinto binary using S-shaped transfer function in Cbinary ijCalculate the fitness of eachCbinary ijUpdate new position of the candidate using (16)End (If)End (For)Cave=Ceqs0+Ceqs1+Ceqs2+Ceqs3/4Construct the equilibrium poolCeqs,pool=Ceqs0,Ceqs2,Ceqs3,CaveAccomplish memory saving (if Iter >1)Assignt=1−iter/maxItera2iter/maxIterusing (12)Fori = 1: number of particles (n)Randomly choose one candidate from the equilibrium pool (vector)Generate random vectors ofλ⃗, r⃗ using (11)ConstructF=a1signr2−0.5e−λt−1 using (11)ConstructGCP=0.5r2≥GP0r2<GPusing (15)ConstructGo=GCP⋅Ceq−λCusing (14)ConstructG=GoF using (13)Update concentrationsC=Ceq+C−Ceq.F+G/ƛV (1- F) using (16)End (For)Iter = Iter + 1End whileReturn candidate with best fitness value


## 6. Results and Discussion

This section summarizes the results of BEOA applied to graph instances that are computed theoretically and the family of snake graphs.


### 6.1. Experimental Results

In this section, the proposed BEOA is compared to the BGWO, BPSO, BWOA, BSMA, BGOA, BAEO, and BEHO algorithms. The algorithms are applied to a path graph, a cycle graph, a triangular snake graph, a double triangular snake graph, (2,k)c4– snake graph, a linear kc4-snake graph, and a nc4 ○ 2pn graph. The algorithm tests and comparisons were performed on the windows 10 Ultimate 64 bit operating system; the processor was an Intel Core i7 running at 16 GB of RAM, the hard drive was a 1TBHDD+1TBSSD, and the code was implemented in MATLAB 2021b. The parameter setting values are presented in Table 1.Table 1
Parameter setting.
AlgorithmsParameter nameValueBEOAParticles numbers50Max iteration300a1, a2, GP, λ[2, 1, 0.5, [0–1]]Number of runs20BGWOSearch agents50Max iteration300a1, a2[2, 0]Number of runs20BPSOSwarm size50C1Increases linearly from 0.5 to 2.5C2Decreases linearly from 2.5 to 0.5Inertia weight (w)0.8Max iteration300Number of runs20BWOAPopulation size50a1[2, 0]a2−2, 1]b1Max iteration300Number of runs20BSMAPopulation size50z0.03Max iteration300Number of runs20BGOAPopulation size50GMaX1GMin0.004Max iteration300Number of runs20BAEOPopulation size50r1,r2, and rrandMax iteration300Number of runs20BEHOElephants number50Clans number5Kept elephants number2The scale factorα0.5The scale factorβ0.1Max iteration300Number of runs20All algorithms have been run 20 times for each graph, and the results are summarized in Tables2–8.Table 2
Results on path graphPn.
Path graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO43γcr22222222t (sec)21.132.329.843.227.958.146.353.2Iteration1112132254γcr33333333t (sec)57.265.143.965.933.176.889.181.7Iteration26382710865γcr44444444t (sec)94.7151.8127.4189.6114.9235.7218.6256.1Iteration4924151039284176γcr55555555t(sec)135.9196.1211.6269.4173.2291.8265.1379.7Iteration93832182643295187γcr66666666t (sec)227.6212.4284.2376.6218.1325.7337.5412.9Iteration121545391852354998γcr77777777t(sec)159.1281.2324.1428.2292.1417.7421.6563.2Iteration852234728634031109γcr88888888t(sec)194.6338.3369.5491.7350.6501.9547.4612.9Iteration2376165942029631110γcr99999999t(sec)238.2391.7412.1570.3211.4588.1682.9659.1Iteration16314935567381241211γcr1010101010101010t(sec)304.9473.7554.03635.9398.5657.4739.5745.8Iteration40677284346283561312γcr1111111111111111t(sec)279.5592.6386.8719.1490.3745.8823.6869.9Iteration242840927754691281413γcr1212121212121212t(sec)196.4689.8716.5835.1583.6809.4904.7972.6Iteration133984715510490621514γcr1313131313131313t(sec)232.8794.4819.2903.6668.19916.31071.51057.2Iteration375692804874141971615γcr1414141414141414t(sec)327.5862.071045.991134.2805.371089.51167.21196.1Iteration2875566839106129831716γcr1515151515151515t(sec)253.9949.21112.71285.3928.71175.31342.61308.9Iteration116380683910612983Table 3
Results on cycle graph.
Cycle graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)32.148.839.856.335.251.763.954.6Iteration1112121355γcr33333333t(sec)91.185.272.1103.952.8125.7149.5111.3Iteration142421817132966γcr44444444t(sec)127.7156.5191.4215.9144.3203.6227.1219.7Iteration61632351137534877γcr55555555t(sec)191.6125.03234.2302.4203.5319.3337.8326.2Iteration195445822964567088γcr66666666t(sec)115.9284.2301.1396.8281.6381.4413.2397.9Iteration32023381631476399γcr77777777t(sec)183.2317.8369.5443.7325.1465.7499.4482.8Iteration17391649326147631010γcr88888888t(sec)248.6386.9412.1506.03212.4536.8574.9601.3Iteration295359784292851091111γcr99999999t(sec)347.8439.3490.03589.7434.9592.5687.1694.7Iteration5264721266987123951212γcr1010101010101010t(sec)381.2472.6596.8654.7509.4671.4756.9741.2Iteration1114250944263381161313γcr1111111111111111t(sec)226.9585.9503.5728.4564.1745.3819.2804.9Iteration938184146198872611414γcr1212121212121212t(sec)295.7703.5756.99801.7638.4815.1910.3895.6Iteration439513216157115961581515γcr1313131313131313t(sec)312.6872.8845.1879.6717.3897.41067.5980.3Iteration16277110926147651061616γcr1414141414141414t(sec)266.2924.4908.7955.3802.6980.21206.71096.1Iteration123239675013546831717γcr1515151515151515t(sec)231.91165.31013.11168.5854.31091.81315.71289.6Iteration511577342908165Table 4
Results on triangular snake graph.
Triangular snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO33γcr22222222t(sec)29.164.145.183.539.886.0495.857.3Iteration1112132356γcr33333333t(sec)53.399.476.4109.568.1123.8162.3117.4Iteration1324238679γcr44444444t(sec)83.8121.297.2135.777.03165.8191.5178.3Iteration2247392113912γcr55555555t(sec)92.2143.9171.3198.2134.9209.8227.1213.5Iteration581126185239211115γcr66666666t(sec)131.4221.6286.9311.8109.2278.1301.4298.3Iteration9132541176782701318γcr77777777t(sec)187.2273.5314.1393.4205.7345.9383.2374.1Iteration21201673315567921521γcr88888888t(sec)233.4301.3423.9458.2290.3401.7469.1418.3Iteration14284165247152781724γcr99999999t(sec)315.1479.1567.2509.4368.9486.5553.8546.7Iteration30253250386687741927γcr1010101010101010t(sec)401.3592.9645.3587.5419.6533.1607.8603.5Iteration194666936084951012130γcr1111111111111111t(sec)519.2708.2742.2665.9536.7598.5691.3679.4Iteration28534082514568942333γcr1212121212121212t(sec)612.4873.1807.1748.3583.5681.5776.4780.6Iteration539554694310885722536γcr1313131313131313t(sec)527.2928.9892.4811.3671.2764.9859.4906.3Iteration257392775884981172739γcr1414141414141414t(sec)631.1815.7985.8994.3728.2841.4904.71021.8Iteration14578963357673932942γcr1515151515151515t(sec)598.41073.21044.21175.1804.1917.51015.31139.5Iteration948751135110667833145γcr1616161616161616t(sec)702.61291.81459.11286.5892.61093.71276.31197.9Iteration1772915738638170Table 5
Results on double triangular snake graph.
Double triangular snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO45γcr22222222t(sec)32.156.279.389.445.292.0281.394.1Iteration11131232710γcr44444444t(sec)82.591.597.1105.394.1130.5109.6107.4Iteration154234291015γcr66666666t(sec)116.3157.4199.4181.9103.1191.475.3184.9Iteration57111361714321320γcr88888888t(sec)194.4248.1273.2265.4227.6263.2230.8271.4Iteration144629191714401625γcr1010101010101010t(sec)231.7376.2327.9341.5284.9380.4312.2359.3Iteration991028152514311930γcr1212121212121212t(sec)361.8295.8415.2497.3342.1449.2428.6418.9Iteration25223846314028342235γcr1414141414141414t(sec)436.8578.4568.1560.7471.8509.1569.3556.2Iteration33364471506347682540γcr1616161616161616t(sec)621.4759.2889.8749.1702.6657.5673.8651.6Iteration276587132438065512845γcr1818181818181818t(sec)745.6956.31034.7913.5827.9795.6768.4780.5Iteration15492635196273593150γcr2020202020202020t(sec)867.51132.61282.61158.8935.2891.4911.7857.4Iteration5411372667683109943455γcr2222222222222222t(sec)991.21439.41545.21282.31091.61018.2966.71026.3Iteration4185119736267811013760γcr2424242424242424t(sec)1023.91674.21617.51376.51180.71227.81149.11304.8Iteration12383856687995834065γcr2626262626262626t(sec)984.11813.81849.91455.31273.21315.91292.71419.3Iteration3557691194510462704370γcr2828282828282828t(sec)1179.21734.72011.21629.81390.51509.21487.31593.8Iteration16497467589669544675γcr3030303030303030t(sec)1045.92006.12273.41937.51511.11784.91673.51760.3Iteration936529034834839Table 6
Results on (2,k)c4-snake graph.
(2,k)c4-snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO68γcr44444444t(sec)35.181.574.265.442.356.948.550.7Iteration111413221116γcr88888888t(sec)93.3134.3117.3109.198.5103.297.6101.8Iteration136825431624γcr1212121212121212t(sec)162.5190.2136.9186.5190.2186.4201.3128.3Iteration3915197131652132γcr1616161616161616t(sec)281.2245.1341.5319.4230.8291.5308.3275.8Iteration15282725183441372640γcr2020202020202020t(sec)356.4307.9474.8381.6301.2387.2393.5369.1Iteration19513954477857613148γcr2424242424242424t(sec)408.7591.4627.6495.3452.6507.2489.4496.5Iteration12804576586549683656γcr2828282828282828t(sec)561.8831.2791.4713.8609.1628.4652.6638.4Iteration28592664338356454164γcr3232323232323232t(sec)637.2955.11011.9970.6736.8721.3781.5806.1Iteration11367453459173514672γcr3636363636363636t(sec)801.91146.81273.81085.3876.9842.6905.1957.4Iteration18476261705945395180γcr4040404040404040t(sec)903.61586.21415.21272.6990.41077.61058.51131.9Iteration375412978468059535688γcr4444444444444444t(sec)1095.51710.41649.61384.31248.51361.81390.71459.4Iteration101217495345340686196γcr4848484848484848t(sec)1207.81824.51922.61572.91391.71538.91571.21598.3Iteration2910969605165704966104γcr5252525252525252t(sec)1176.92017.62196.71738.11473.41714.51749.81824.5Iteration2583115723640673171112γcr5656565656565656t(sec)1311.72186.52338.81899.41612.91873.81971.11912.4Iteration177661554261385176120γcr6060606060606060t(sec)1455.82252.32513.12047.31739.52096.42134.72086.3Iteration1448758125344742Table 7
Results on linearkc4-snake graph.
Linearkc4-snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)26.148.259.380.736.273.162.357.1Iteration1113123178γcr44444444t(sec)71.3115.387.4109.167.890.575.876.3Iteration132523421012γcr66666666t(sec)165.4198.7131.2148.994.6121.110.191.6Iteration58210481391316γcr88888888t(sec)207.5286.3245.6269.3233.5250.2262.8243.9Iteration9191423161319121620γcr1010101010101010t(sec)335.8369.1312.8352.8340.9359.3381.4361.8Iteration15222540281736271924γcr1212121212121212\t(sec)399.3528.4496.7461.3408.1420.7473.5451.9Iteration13394468362549322228γcr1414141414141414t(sec)482.2690.8702.4583.1571.9539.4552.9502.5Iteration28525957443663402532γcr1616161616161616t(sec)596.4531.9853.1675.8610.3621.9643.4619.7Iteration15185865305222372836γcr1818181818181818t(sec)711.9825.2949.5784.5739.1760.3726.1704.9Iteration192610982547041583140γcr2020202020202020t(sec)842.11094.51015.4917.3901.9938.8952.7986.1Iteration42988450406138453444γcr2222222222222222t(sec)957.51238.11284.71149.81054.61127.31014.91096.5Iteration34747164512432393748γcr2424242424242424t(sec)1095.11452.41457.41323.61179.21315.81205.21273.9Iteration12929856382959434052γcr2626262626262626t(sec)1264.21698.91736.21494.81321.61429.51339.41407.2Iteration37635931473644514356γcr2828282828282828t(sec)981.41759.21977.21607.31458.81537.91503.41591.6Iteration23484237293452474660γcr3232323232323232t(sec)1149.31904.42193.81725.91631.61729.21681.51708.1Iteration1539675238453135Table 8
Results onnc4 ○ 2pn graph.
nc4 ○ 2pn graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)19.231.427.149.843.962.554.847.5Iteration11142252810γcr55555555t(sec)51.495.846.584.366.493.899.180.6Iteration232754961216γcr66666666t(sec)99.3148.5103.4112.6101.7139.3128.4119.2Iteration859141087131622γcr88888888t(sec)145.4259.2131.2181.9196.5204.7171.3165.7Iteration13181523193214252028γcr1010101010101010t(sec)234.1374.1285.8299.1271.8262.3256.9240.4Iteration27233258364129442434γcr1212121212121212t(sec)315.4452.3432.2467.4349.3398.5362.1335.7Iteration34694871554637502840γcr1414141414141414t(sec)452.2561.8590.3594.3512.8529.2478.9496.4Iteration19158733285745383246γcr1616161616161616t(sec)607.5705.1745.1718.9571.6639.5595.1624.9Iteration254310385376459413652γcr1818181818181818t(sec)748.4890.3913.6794.3789.2802.6757.4763.8Iteration17767162304138564058γcr2020202020202020t(sec)873.11087.81169.41015.6918.31048.9961.41091.1Iteration311215240254662484464γcr2222222222222222t(sec)994.51264.21325.71293.81076.11181.41074.21238.4Iteration39879863718057514870γcr2424242424242424t(sec)1127.21416.51694.81470.31213.91309.11256.91395.8Iteration224963134365168775276γcr2626262626262626t(sec)1209.41634.21383.21596.41408.51484.61393.41504.1Iteration15325886296254395682γcr2828282828282828t(sec)1028.41913.51894.11852.31543.81631.91519.21665.5Iteration19767179375546436088γcr3030303030303030t(sec)1125.32026.92257.52067.41712.91822.61705.11839.3Iteration1051946126425038The tables are organized as follows: The first three columns contain the number of nodesN, the number of edges M, the connected domination resolving number γcr, and the CPU time (t) used to indicate the exactly connected domination resolving number and iteration: the average number of iterations for finishing the algorithms to achieve the best solution, respectively.Table2 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected domination resolving number for path graph Pn, 4 ≤ n ≤ 17, and BEOA has reached an optimal solution.Table3 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for cycle graph Cn, 4 ≤ n ≤ 17, and BEOA has reached an optimal solution.Table4 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for triangular snake graph Tn, 3 ≤ n ≤ 33, and BEOA has reached an optimal solution.Table5 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for double triangular snake graph DTn, 4 ≤ n ≤ 46.Table6 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for (2,k)c4– snake graph, 1 ≤ k ≤ 15 and 6 ≤ n ≤ 76.Table7 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for linear kc4-snake graph, 1 ≤ k ≤ 15 and 4 ≤ n ≤ 46.Table8 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for nc4 ○ 2Pn graph and 4 ≤ n ≤ 60.


### 6.2. Comparison

To further demonstrate the excellence of proposed BEOA, we choose BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO algorithms to conduct experiments under the same conditions and compared the results.The results on graphs are shown in Tables2–8, which indicate that the proposed BEOA algorithm outperforms other algorithms on graphs, reaching 253.87 sec in BEOA, 949.24 sec in BGWO,1112.73 sec in BPSO,1285.3 sec in BWO, 928.7 sec in BSMO,1175.3 sec in BGO,1342.6 sec in BAEO, and 1308.9 sec in BEHO for path graph, 231.93 sec in BEOA, 1165.33 sec in BGWO,1013.1 sec in BPSO,1168.5 sec in BWO,854.3 sec in BSMO,1091.8 sec in BGO,1315.7 sec in BAEO, and 1289.6 sec in BEHO for cycle graph, 702.6 sec in BEOA,1291.8 sec in BGWO,1459.1sec in BPSO,1286.5 sec in BWO, 892.6 sec in BSMO, 1093.7 sec in BGO,1276.3 sec in BAEO, and 1197.9 sec in BEHO for triangular snake graph, and 1045.9 sec in BEOA, 2006.1sec in BGWO, 2273.4 sec in BPSO 1937.5 sec in BWO, 1511.1 sec in BSMO, 1784.9 sec in BGO,1673.5 sec in BAEO, and 1760.3 sec in BEHO for double triangular snake graph, 1455.8 sec in BEOA, 2252.3 sec in BGWO, 2513.1 sec in BPSO, 2047.3 sec in BWO, 1739.5 sec in BSMO, 2096.4 sec in BGO, 2134.7 sec in BAEO, and 2086.3 sec in BEHO for (2,k)c4– snake graph, 1149.1 sec in BEOA, 1904.4 sec in BGWO, 2193.8 sec in BPSO, 1725.9 sec in BWO, 1631.6 sec in BSMO, 1729.2 sec in BGO, 1681.5 sec in BAEO, and 1708.1 sec in BEHO for linear kc4-snake graph, and 1125.3 sec in BEOA, 2026.9 sec in BGWO, 2257.5 sec in BPSO, 2067.4 sec in BWO, 1712.9 sec in BSMO, 1822.6 sec in BGO, 1705.1 sec in BAEO, and 1839.3 sec in BEHO for nc4 ○ 2pn graph. It proves the correctness and superiority of the proposed BEOA.Figures2–8 show the superiority of the proposed BEOA on the BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO according to the connected domination resolving number.Figure 2
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for path graph.Figure 3
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for cycle graph.Figure 4
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for triangular snake graph.Figure 5
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for double triangular snake graph.Figure 6
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for (2,k)c4 – snake graph.Figure 7
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for linearkc4-snake graph.Figure 8
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number fornc4 ○ 2pn graph.


## 6.1. Experimental Results

In this section, the proposed BEOA is compared to the BGWO, BPSO, BWOA, BSMA, BGOA, BAEO, and BEHO algorithms. The algorithms are applied to a path graph, a cycle graph, a triangular snake graph, a double triangular snake graph, (2,k)c4– snake graph, a linear kc4-snake graph, and a nc4 ○ 2pn graph. The algorithm tests and comparisons were performed on the windows 10 Ultimate 64 bit operating system; the processor was an Intel Core i7 running at 16 GB of RAM, the hard drive was a 1TBHDD+1TBSSD, and the code was implemented in MATLAB 2021b. The parameter setting values are presented in Table 1.Table 1
Parameter setting.
AlgorithmsParameter nameValueBEOAParticles numbers50Max iteration300a1, a2, GP, λ[2, 1, 0.5, [0–1]]Number of runs20BGWOSearch agents50Max iteration300a1, a2[2, 0]Number of runs20BPSOSwarm size50C1Increases linearly from 0.5 to 2.5C2Decreases linearly from 2.5 to 0.5Inertia weight (w)0.8Max iteration300Number of runs20BWOAPopulation size50a1[2, 0]a2−2, 1]b1Max iteration300Number of runs20BSMAPopulation size50z0.03Max iteration300Number of runs20BGOAPopulation size50GMaX1GMin0.004Max iteration300Number of runs20BAEOPopulation size50r1,r2, and rrandMax iteration300Number of runs20BEHOElephants number50Clans number5Kept elephants number2The scale factorα0.5The scale factorβ0.1Max iteration300Number of runs20All algorithms have been run 20 times for each graph, and the results are summarized in Tables2–8.Table 2
Results on path graphPn.
Path graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO43γcr22222222t (sec)21.132.329.843.227.958.146.353.2Iteration1112132254γcr33333333t (sec)57.265.143.965.933.176.889.181.7Iteration26382710865γcr44444444t (sec)94.7151.8127.4189.6114.9235.7218.6256.1Iteration4924151039284176γcr55555555t(sec)135.9196.1211.6269.4173.2291.8265.1379.7Iteration93832182643295187γcr66666666t (sec)227.6212.4284.2376.6218.1325.7337.5412.9Iteration121545391852354998γcr77777777t(sec)159.1281.2324.1428.2292.1417.7421.6563.2Iteration852234728634031109γcr88888888t(sec)194.6338.3369.5491.7350.6501.9547.4612.9Iteration2376165942029631110γcr99999999t(sec)238.2391.7412.1570.3211.4588.1682.9659.1Iteration16314935567381241211γcr1010101010101010t(sec)304.9473.7554.03635.9398.5657.4739.5745.8Iteration40677284346283561312γcr1111111111111111t(sec)279.5592.6386.8719.1490.3745.8823.6869.9Iteration242840927754691281413γcr1212121212121212t(sec)196.4689.8716.5835.1583.6809.4904.7972.6Iteration133984715510490621514γcr1313131313131313t(sec)232.8794.4819.2903.6668.19916.31071.51057.2Iteration375692804874141971615γcr1414141414141414t(sec)327.5862.071045.991134.2805.371089.51167.21196.1Iteration2875566839106129831716γcr1515151515151515t(sec)253.9949.21112.71285.3928.71175.31342.61308.9Iteration116380683910612983Table 3
Results on cycle graph.
Cycle graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)32.148.839.856.335.251.763.954.6Iteration1112121355γcr33333333t(sec)91.185.272.1103.952.8125.7149.5111.3Iteration142421817132966γcr44444444t(sec)127.7156.5191.4215.9144.3203.6227.1219.7Iteration61632351137534877γcr55555555t(sec)191.6125.03234.2302.4203.5319.3337.8326.2Iteration195445822964567088γcr66666666t(sec)115.9284.2301.1396.8281.6381.4413.2397.9Iteration32023381631476399γcr77777777t(sec)183.2317.8369.5443.7325.1465.7499.4482.8Iteration17391649326147631010γcr88888888t(sec)248.6386.9412.1506.03212.4536.8574.9601.3Iteration295359784292851091111γcr99999999t(sec)347.8439.3490.03589.7434.9592.5687.1694.7Iteration5264721266987123951212γcr1010101010101010t(sec)381.2472.6596.8654.7509.4671.4756.9741.2Iteration1114250944263381161313γcr1111111111111111t(sec)226.9585.9503.5728.4564.1745.3819.2804.9Iteration938184146198872611414γcr1212121212121212t(sec)295.7703.5756.99801.7638.4815.1910.3895.6Iteration439513216157115961581515γcr1313131313131313t(sec)312.6872.8845.1879.6717.3897.41067.5980.3Iteration16277110926147651061616γcr1414141414141414t(sec)266.2924.4908.7955.3802.6980.21206.71096.1Iteration123239675013546831717γcr1515151515151515t(sec)231.91165.31013.11168.5854.31091.81315.71289.6Iteration511577342908165Table 4
Results on triangular snake graph.
Triangular snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO33γcr22222222t(sec)29.164.145.183.539.886.0495.857.3Iteration1112132356γcr33333333t(sec)53.399.476.4109.568.1123.8162.3117.4Iteration1324238679γcr44444444t(sec)83.8121.297.2135.777.03165.8191.5178.3Iteration2247392113912γcr55555555t(sec)92.2143.9171.3198.2134.9209.8227.1213.5Iteration581126185239211115γcr66666666t(sec)131.4221.6286.9311.8109.2278.1301.4298.3Iteration9132541176782701318γcr77777777t(sec)187.2273.5314.1393.4205.7345.9383.2374.1Iteration21201673315567921521γcr88888888t(sec)233.4301.3423.9458.2290.3401.7469.1418.3Iteration14284165247152781724γcr99999999t(sec)315.1479.1567.2509.4368.9486.5553.8546.7Iteration30253250386687741927γcr1010101010101010t(sec)401.3592.9645.3587.5419.6533.1607.8603.5Iteration194666936084951012130γcr1111111111111111t(sec)519.2708.2742.2665.9536.7598.5691.3679.4Iteration28534082514568942333γcr1212121212121212t(sec)612.4873.1807.1748.3583.5681.5776.4780.6Iteration539554694310885722536γcr1313131313131313t(sec)527.2928.9892.4811.3671.2764.9859.4906.3Iteration257392775884981172739γcr1414141414141414t(sec)631.1815.7985.8994.3728.2841.4904.71021.8Iteration14578963357673932942γcr1515151515151515t(sec)598.41073.21044.21175.1804.1917.51015.31139.5Iteration948751135110667833145γcr1616161616161616t(sec)702.61291.81459.11286.5892.61093.71276.31197.9Iteration1772915738638170Table 5
Results on double triangular snake graph.
Double triangular snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO45γcr22222222t(sec)32.156.279.389.445.292.0281.394.1Iteration11131232710γcr44444444t(sec)82.591.597.1105.394.1130.5109.6107.4Iteration154234291015γcr66666666t(sec)116.3157.4199.4181.9103.1191.475.3184.9Iteration57111361714321320γcr88888888t(sec)194.4248.1273.2265.4227.6263.2230.8271.4Iteration144629191714401625γcr1010101010101010t(sec)231.7376.2327.9341.5284.9380.4312.2359.3Iteration991028152514311930γcr1212121212121212t(sec)361.8295.8415.2497.3342.1449.2428.6418.9Iteration25223846314028342235γcr1414141414141414t(sec)436.8578.4568.1560.7471.8509.1569.3556.2Iteration33364471506347682540γcr1616161616161616t(sec)621.4759.2889.8749.1702.6657.5673.8651.6Iteration276587132438065512845γcr1818181818181818t(sec)745.6956.31034.7913.5827.9795.6768.4780.5Iteration15492635196273593150γcr2020202020202020t(sec)867.51132.61282.61158.8935.2891.4911.7857.4Iteration5411372667683109943455γcr2222222222222222t(sec)991.21439.41545.21282.31091.61018.2966.71026.3Iteration4185119736267811013760γcr2424242424242424t(sec)1023.91674.21617.51376.51180.71227.81149.11304.8Iteration12383856687995834065γcr2626262626262626t(sec)984.11813.81849.91455.31273.21315.91292.71419.3Iteration3557691194510462704370γcr2828282828282828t(sec)1179.21734.72011.21629.81390.51509.21487.31593.8Iteration16497467589669544675γcr3030303030303030t(sec)1045.92006.12273.41937.51511.11784.91673.51760.3Iteration936529034834839Table 6
Results on (2,k)c4-snake graph.
(2,k)c4-snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO68γcr44444444t(sec)35.181.574.265.442.356.948.550.7Iteration111413221116γcr88888888t(sec)93.3134.3117.3109.198.5103.297.6101.8Iteration136825431624γcr1212121212121212t(sec)162.5190.2136.9186.5190.2186.4201.3128.3Iteration3915197131652132γcr1616161616161616t(sec)281.2245.1341.5319.4230.8291.5308.3275.8Iteration15282725183441372640γcr2020202020202020t(sec)356.4307.9474.8381.6301.2387.2393.5369.1Iteration19513954477857613148γcr2424242424242424t(sec)408.7591.4627.6495.3452.6507.2489.4496.5Iteration12804576586549683656γcr2828282828282828t(sec)561.8831.2791.4713.8609.1628.4652.6638.4Iteration28592664338356454164γcr3232323232323232t(sec)637.2955.11011.9970.6736.8721.3781.5806.1Iteration11367453459173514672γcr3636363636363636t(sec)801.91146.81273.81085.3876.9842.6905.1957.4Iteration18476261705945395180γcr4040404040404040t(sec)903.61586.21415.21272.6990.41077.61058.51131.9Iteration375412978468059535688γcr4444444444444444t(sec)1095.51710.41649.61384.31248.51361.81390.71459.4Iteration101217495345340686196γcr4848484848484848t(sec)1207.81824.51922.61572.91391.71538.91571.21598.3Iteration2910969605165704966104γcr5252525252525252t(sec)1176.92017.62196.71738.11473.41714.51749.81824.5Iteration2583115723640673171112γcr5656565656565656t(sec)1311.72186.52338.81899.41612.91873.81971.11912.4Iteration177661554261385176120γcr6060606060606060t(sec)1455.82252.32513.12047.31739.52096.42134.72086.3Iteration1448758125344742Table 7
Results on linearkc4-snake graph.
Linearkc4-snake graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)26.148.259.380.736.273.162.357.1Iteration1113123178γcr44444444t(sec)71.3115.387.4109.167.890.575.876.3Iteration132523421012γcr66666666t(sec)165.4198.7131.2148.994.6121.110.191.6Iteration58210481391316γcr88888888t(sec)207.5286.3245.6269.3233.5250.2262.8243.9Iteration9191423161319121620γcr1010101010101010t(sec)335.8369.1312.8352.8340.9359.3381.4361.8Iteration15222540281736271924γcr1212121212121212\t(sec)399.3528.4496.7461.3408.1420.7473.5451.9Iteration13394468362549322228γcr1414141414141414t(sec)482.2690.8702.4583.1571.9539.4552.9502.5Iteration28525957443663402532γcr1616161616161616t(sec)596.4531.9853.1675.8610.3621.9643.4619.7Iteration15185865305222372836γcr1818181818181818t(sec)711.9825.2949.5784.5739.1760.3726.1704.9Iteration192610982547041583140γcr2020202020202020t(sec)842.11094.51015.4917.3901.9938.8952.7986.1Iteration42988450406138453444γcr2222222222222222t(sec)957.51238.11284.71149.81054.61127.31014.91096.5Iteration34747164512432393748γcr2424242424242424t(sec)1095.11452.41457.41323.61179.21315.81205.21273.9Iteration12929856382959434052γcr2626262626262626t(sec)1264.21698.91736.21494.81321.61429.51339.41407.2Iteration37635931473644514356γcr2828282828282828t(sec)981.41759.21977.21607.31458.81537.91503.41591.6Iteration23484237293452474660γcr3232323232323232t(sec)1149.31904.42193.81725.91631.61729.21681.51708.1Iteration1539675238453135Table 8
Results onnc4 ○ 2pn graph.
nc4 ○ 2pn graphNMBEOABGWOBPSOBWOBSMOBGOBAEOBEHO44γcr22222222t(sec)19.231.427.149.843.962.554.847.5Iteration11142252810γcr55555555t(sec)51.495.846.584.366.493.899.180.6Iteration232754961216γcr66666666t(sec)99.3148.5103.4112.6101.7139.3128.4119.2Iteration859141087131622γcr88888888t(sec)145.4259.2131.2181.9196.5204.7171.3165.7Iteration13181523193214252028γcr1010101010101010t(sec)234.1374.1285.8299.1271.8262.3256.9240.4Iteration27233258364129442434γcr1212121212121212t(sec)315.4452.3432.2467.4349.3398.5362.1335.7Iteration34694871554637502840γcr1414141414141414t(sec)452.2561.8590.3594.3512.8529.2478.9496.4Iteration19158733285745383246γcr1616161616161616t(sec)607.5705.1745.1718.9571.6639.5595.1624.9Iteration254310385376459413652γcr1818181818181818t(sec)748.4890.3913.6794.3789.2802.6757.4763.8Iteration17767162304138564058γcr2020202020202020t(sec)873.11087.81169.41015.6918.31048.9961.41091.1Iteration311215240254662484464γcr2222222222222222t(sec)994.51264.21325.71293.81076.11181.41074.21238.4Iteration39879863718057514870γcr2424242424242424t(sec)1127.21416.51694.81470.31213.91309.11256.91395.8Iteration224963134365168775276γcr2626262626262626t(sec)1209.41634.21383.21596.41408.51484.61393.41504.1Iteration15325886296254395682γcr2828282828282828t(sec)1028.41913.51894.11852.31543.81631.91519.21665.5Iteration19767179375546436088γcr3030303030303030t(sec)1125.32026.92257.52067.41712.91822.61705.11839.3Iteration1051946126425038The tables are organized as follows: The first three columns contain the number of nodesN, the number of edges M, the connected domination resolving number γcr, and the CPU time (t) used to indicate the exactly connected domination resolving number and iteration: the average number of iterations for finishing the algorithms to achieve the best solution, respectively.Table2 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected domination resolving number for path graph Pn, 4 ≤ n ≤ 17, and BEOA has reached an optimal solution.Table3 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for cycle graph Cn, 4 ≤ n ≤ 17, and BEOA has reached an optimal solution.Table4 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for triangular snake graph Tn, 3 ≤ n ≤ 33, and BEOA has reached an optimal solution.Table5 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for double triangular snake graph DTn, 4 ≤ n ≤ 46.Table6 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for (2,k)c4– snake graph, 1 ≤ k ≤ 15 and 6 ≤ n ≤ 76.Table7 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for linear kc4-snake graph, 1 ≤ k ≤ 15 and 4 ≤ n ≤ 46.Table8 shows a comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for nc4 ○ 2Pn graph and 4 ≤ n ≤ 60.


## 6.2. Comparison

To further demonstrate the excellence of proposed BEOA, we choose BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO algorithms to conduct experiments under the same conditions and compared the results.The results on graphs are shown in Tables2–8, which indicate that the proposed BEOA algorithm outperforms other algorithms on graphs, reaching 253.87 sec in BEOA, 949.24 sec in BGWO,1112.73 sec in BPSO,1285.3 sec in BWO, 928.7 sec in BSMO,1175.3 sec in BGO,1342.6 sec in BAEO, and 1308.9 sec in BEHO for path graph, 231.93 sec in BEOA, 1165.33 sec in BGWO,1013.1 sec in BPSO,1168.5 sec in BWO,854.3 sec in BSMO,1091.8 sec in BGO,1315.7 sec in BAEO, and 1289.6 sec in BEHO for cycle graph, 702.6 sec in BEOA,1291.8 sec in BGWO,1459.1sec in BPSO,1286.5 sec in BWO, 892.6 sec in BSMO, 1093.7 sec in BGO,1276.3 sec in BAEO, and 1197.9 sec in BEHO for triangular snake graph, and 1045.9 sec in BEOA, 2006.1sec in BGWO, 2273.4 sec in BPSO 1937.5 sec in BWO, 1511.1 sec in BSMO, 1784.9 sec in BGO,1673.5 sec in BAEO, and 1760.3 sec in BEHO for double triangular snake graph, 1455.8 sec in BEOA, 2252.3 sec in BGWO, 2513.1 sec in BPSO, 2047.3 sec in BWO, 1739.5 sec in BSMO, 2096.4 sec in BGO, 2134.7 sec in BAEO, and 2086.3 sec in BEHO for (2,k)c4– snake graph, 1149.1 sec in BEOA, 1904.4 sec in BGWO, 2193.8 sec in BPSO, 1725.9 sec in BWO, 1631.6 sec in BSMO, 1729.2 sec in BGO, 1681.5 sec in BAEO, and 1708.1 sec in BEHO for linear kc4-snake graph, and 1125.3 sec in BEOA, 2026.9 sec in BGWO, 2257.5 sec in BPSO, 2067.4 sec in BWO, 1712.9 sec in BSMO, 1822.6 sec in BGO, 1705.1 sec in BAEO, and 1839.3 sec in BEHO for nc4 ○ 2pn graph. It proves the correctness and superiority of the proposed BEOA.Figures2–8 show the superiority of the proposed BEOA on the BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO according to the connected domination resolving number.Figure 2
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for path graph.Figure 3
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for cycle graph.Figure 4
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for triangular snake graph.Figure 5
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for double triangular snake graph.Figure 6
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for (2,k)c4 – snake graph.Figure 7
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number for linearkc4-snake graph.Figure 8
Comparison between BEOA, BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO for computing connected dominating resolving number fornc4 ○ 2pn graph.


## 7. Conclusion

In this paper, a binary variant of the basic equilibrium optimization algorithm BEOA for determining the minimum connected domination resolving set of graphs and compared to BGWO, BPSO, BWO, BSMO, BGO, BAEO, and BEHO. Comparisons were performed on the graphs: a path graph, cycle graph, triangular snake graph, double triangular snake graph, (2,k)c4– snake graph, linear kc4-snake graph, and nc4 ○ 2pn graph. Experimental results and their analysis confirmed the superiority of the proposed BEOA for solving the connected domination metric dimension problem.For further work in the future, we plan to compute other variants of metric dimension by other metaheuristic algorithms and compare them with competitive algorithms.



---

*Source: 6076369-2022-10-06.xml*