Abstract
In this article, we look at the NPhard problem of determining the minimum independent domination metric dimension of graphs. A vertex set $B$ of a connected graph $G(V,E)$ resolves $G$ if every vertex of $G$ is uniquely recognized by its vector of distances to the vertices in $B$. If there are no neighboring vertices in a resolving set $B$ of $G$, then $B$ is independent. Every vertex of $G$ that does not belong to $B$ must be a neighbor of at least one vertex in $B$ for a resolving set to be dominant. The metric dimension of $G$, independent metric dimension of $G$, and independent dominant metric dimension of $G$ are, respectively, the cardinality of the smallest resolving set of $G$, the minimal independent resolving set, and the minimal independent domination resolving set. We propose the first attempt to use a binary version of the Rat Swarm Optimizer Algorithm (BRSOA) to heuristically calculate the smallest independent dominant resolving set of graphs. The search agent of BRSOA are binaryencoded and used to identify which one of the vertices of the graph belongs to the independent domination resolving set. The feasibility is enforced by repairing search agent such that an additional vertex created from vertices of $G$ is added to $B$, and this repairing process is repeated until $B$ becomes the independent domination resolving set. Using theoretically computed graph findings and comparisons to competing methods, the proposed BRSOA is put to the test. BRSOA surpasses the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer (BPSO), the binary Whale Optimizer (BWOA), the binary Gravitational Search Algorithm (BGSA), and the binary MothFlame Optimization (BMFO), according to computational results and their analysis.
Highlights
 Recognizing the NPhard problem of determining the minimum independent domination metric dimension of graphs.
 Proposing a first attempt to use a binary version of the Rat Swarm Optimizer Algorithm (BRSOA) to heuristically calculate the smallest independent dominant resolving set of graphs.
 Using theoretically computed graph findings and comparisons to competing methods, the proposed BRSOA is put to the test, which has confirmed its superiority over the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer, the binary Whale Optimizer, the binary Gravitational Search Algorithm, and the binary MothFlame Optimization.
1. Introduction
Independent graph dominance numbers have recently been introduced in [1]. Robot navigation [24], network discovery and verification [5], localization of wireless sensor networks [6], combinatorial optimization [7], and applications to pharmaceutical chemistry [8] are only a few areas where metric dimension is used. Domination theory is applied in wireless communication networks [9], electrical networks [10], Backbone based routing [11], or spine based routing [12, 13] and chemical structures [14]. The independent domination set with the minimum cardinality is a logical choice for usage in any network type for information transmission.
2. Problem description
Let $d(u,v)$ be the shortest path between two vertices $u,v\in V\left(G\right)$ in the connected graph $G=(V,E)$. If the representation $r\left(vB\right)=\left(d\right(v,{x}_{1}),d(v,{x}_{2}),...,d(v,{x}_{k}\left)\right)$ is unique for every $v\in V\left(G\right)$, then the ordered vertex set $B=\{{x}_{1},{x}_{2},...,{x}_{k}\}\subseteq V\left(G\right)$ is a resolving set of $G$. If every vertex of $V\backslash B$ has at least one neighbor that belongs to $B$, then $B$ is a dominating resolving set of $G$. A dominating resolving set $B$ is independent if no two vertices in $B$ are adjacent.
Let $Card\left(X\right)$ stand for the cardinality of a set $X$. The metric dimension of $G$, denoted as $dim\left(G\right)$, the domination metric dimension of $G$, denoted as $Ddim\left(G\right)$, and the independent domination metric dimension of $G$, denoted as ${\gamma}_{ir}\left(G\right)$, are as follows:
– $dim\left(G\right)=min\left\{Card\right(B):B$is a resolving set of$G\},$
– $Ddim\left(G\right)=min\left\{Card\right(B):B$is a domination resolving set of$G\},$
– ${\gamma}_{ir}\left(G\right)=min\left\{Card\right(B):B$is an independent dominating resolving set of$G\}.$
Example 2.1. The set $B=\{{v}_{2},{v}_{4},{v}_{6}\}$ is a minimal resolving set for the friendship graph ${F}_{{r}_{7}}$ given in Fig. 1, and hence $dim\left({F}_{{r}_{7}}\right)=3$. Here, $B$ is also a minimal domination resolving set since every vertex of$V\u29f5B$ has at least one neighbor that belongs to $B$. For example, ${v}_{3}$ is adjacent to ${v}_{1}$_{}and ${v}_{2}$. Also, ${v}_{5}$ adjacent to ${v}_{1}$ and ${v}_{4}$. In the same regard, ${v}_{7}$ adjacent to ${v}_{1}$ and ${v}_{6}$. Also, ${v}_{1}$_{}adjacent to ${v}_{2}$, ${v}_{3}$, ${v}_{4}$, ${v}_{5}$, ${v}_{6}$ and ${v}_{7}$, and so $Ddim\left({F}_{{r}_{7}}\right)=3$. On the other hand, $B$ is also independent domination resolving set of ${F}_{{r}_{7}}$. The set $B=\{{v}_{2},{v}_{4},{v}_{6}\}$ is a minimal independent domination resolving set of ${F}_{{r}_{7}}$, so ${\gamma}_{ir}\left({F}_{{r}_{7}}\right)=3$.
Fig. 1Friendship graph Fr7
Three elements are combined in the independent domination metric dimension problem: independent, dominance, and metric dimension of graphs. Integer programming is used to discuss the difficulty of determining the metric dimension of a graph $G$ [8]. Let $D=\left[{d}_{ij}\right]$ be the distance matrix of $G$, ${d}_{ij}=d({v}_{i},{v}_{j})$ for $1\le i$, $j\le n$. For ${x}_{i}\in \{0,1\}$, $1\le i\le n$, the function $F$ is defined by $F({x}_{1},{x}_{2},...,{x}_{n})={x}_{1}+{x}_{2}+\xb7\xb7\xb7+{x}_{n}.$
Minimizing $F$ subject to the $\left(\begin{array}{c}n\\ 2\end{array}\right)$ constraints $\left{d}_{i1}{d}_{j1}\right{x}_{1}+\left{d}_{i2}{d}_{j2}\right{x}_{2}+\dots +\left{d}_{in}{d}_{jn}\right{x}_{n}>0$ is equivalent to finding a basis in the sense that if ${x}_{1}^{\text{'}},{x}_{2}^{\text{'}},\dots ,{x}_{n}^{\text{'}}$ is a set of values for which $F$ reaches its minimum, for $1\le i<j\le n$. Then $B=\{{v}_{i},{x}_{i}^{\text{'}}=1\}$ is a basis for $G$ and conversely, if $B=\{{v}_{i1},{v}_{i2},\dots ,{v}_{in}\}$ is a basis for $G$ and if we define:
then $F({x}_{1}^{\text{'}}$,${x}_{2}^{\text{'}},\dots ,{x}_{n}^{\text{'}})$is a minimum subject to the given constraints.
Both the metric dimension problem and the dominant set problem are NPcomplete [15, 16]. As a result, the independent domination metric dimension ${\gamma}_{ir}\left(G\right)$ is a typical NPcomplete problem that involves determining if ${\gamma}_{ir}\left(G\right)\le K$ for a given graph $G$ and input $K$. The remaining part of the paper is structured as follows: A literature review is presented in Section 3. In Section 4, the Rat Swarm Optimizer Algorithm is introduced. The BRSOA for calculating the independent domination metric dimension is provided in Section 5. Results of calculations are reported in Section 6. Section 7 presents the conclusion and recommendations for future work.
3. Literature review
For a number of graphs in the literature, the metric dimension, domination metric dimension, and independent domination metric dimension are all theoretically specified. Following is a brief summary of the key recently discovered theoretical metric dimension results [1725]. The metric dimension of subdivisions of several graphs, including the Lilly graph, the Tadpole graph, and the special trees star tree, bistar tree, and coconut tree is determined theoretically in [17], the bary centric subdivision of Möbius ladders and the generalized Petersen multigraphs in [18], trapezoid network, $Z\left({P}_{n}\right)$ network, open ladder network, tortoise network in [19], French windmill graph and Dutch windmill graph in [20], total graph of path power three and four in [21], two types of bicyclic graphs in [22], Mobius Ladder in [23], power of paths and complement of paths in [24], and Kayak Paddles graph and Cycles with chord in [25].
Theoretically, the independent metric dimensions are identified in [26, 27]. Cartesian product and corona of graphs are determined in [26], finite projective planes, finite biplanes in [27] and Titanium dioxide nanotube in [28]. The independent domination metric dimensions of the path graph, cycle graph, friendship graph, helm graph, and fan graph are determined theoretically in [1]. In [29, 30], the dominant metric dimension is found theoretically. The Path graph, cycle graph, star graph, complete graph, and complete bipartite graph are determined in [29], the corona product graph of $G$ and $H$ is studied whenever $H$ is a path graph, and the cycle graph, complete bipartite graph, complete graph, and star graph are determined in [30]. The connected domination metric dimensions of the complete graph, path graph, and cycle graph are determined theoretically in [31]. To compute the metric dimension problem heuristically, however, only a small number of algorithms have been presented [3234]. For determining the metric dimension of numerous classes of graph instances, such as pseudoBoolean, crew scheduling, and graph coloring, a genetic algorithm has been proposed in [32]. A limited number of distinct individuals with the same objective value, the binary representation, frozen gene mutation, and the caching technique were all used. Infeasible individuals are changed by the addition of the required nodes in order to become feasible. In [33], Particle Swarm Optimization is used for determining the metric dimension where an infeasible particle is mended by adding some vertices until the particle becomes feasible and a realvalued vector of vertices is converted to a binaryvalued vector using a linear function. The Particle Swarm Optimization is tested by computing the metric dimension of hypercube graphs. In order to enhance the current upper bounds in [34], a variable neighborhood search method has been suggested for tackling metric dimension and minimal doubly resolving set problems. The metric dimension problem and the minimal doubly resolving set problem are divided into a series of sub problems with an auxiliary objective function as the foundation for the variable neighborhood search method. Additionally, the equivalent new integer linear programming formulations for both problems are suggested. The connected domination metric dimension problem is resolved here by encoding and adapting the operations of the equilibrium optimization algorithm. Using theoretically computed graph results, the proposed binary equilibrium optimization algorithm is put to the test and contrasted with competing techniques. Also see more details in the literature [3538], and some future notions may be applied to some applications like [3941]. In the binary forms of the metaheuristics, a transfer function plays a crucial role, according to Mirjalili and Lewis in [42]. It has a major effect on both the balance between exploration and exploitation and the avoidance of local optima. In 2013, Sharafi et al. [43] altered the definition of the velocity vector to the probability of mutation in each cat dimension, introduced a transfer function to the tracking mode of the cat swarm algorithm, and converted the continuous cat swarm algorithm into a discrete binary cat swarm algorithm. A binary variant of the bat technique, which is likewise a probability value that uses a transfer function to convert velocity data to updated positions, was proposed by Mirjalili et al. [44] in 2014. A discrete binary bat method (BINBA) was proposed by Sabba and Chikhi [45] in the same year to solve binary space optimization problems.
4. Rat swarm optimizer (RSO) algorithm
4.1. Inspiration
Longtailed, mediumsized rodents with different sizes and weights include rats. Black rats and brown rats are the two main species of rat. In the family of rats, male rats are referred to as bucks and female rats as does. In general, rats are naturally socially intelligent. They train one another and engage in a variety of sports, including boxing, chasing, jumping, and tumbling. Rats are social, territorial creatures that coexist in households with both males and females. Rats are frequently quite aggressive in their behavior, which may cause the demise of some animals. This work's primary motive for pursuing and fighting with prey is this aggressive behavior. Rat chasing and hunting behaviors are mathematically modeled in this study in order to create the RSO algorithm and carry out optimization.
4.2. Mathematical model and optimization algorithm
This section explains the chasing and fighting behaviors of rats. The suggested RSO algorithm is then described.
4.2.1. Chasing the prey
Rats are typically sociable creatures that hunt their prey in packs using social agonistic behavior. The position of the prey must be known by the optimal search agent in order to mathematically define this behavior. With regard to the best search agent found thus far, the other search agents can update their places. In this mechanism, the following equations are proposed:
where ${\overrightarrow{P}}_{i}\left(x\right)$ is the best optimal solution and ${\overrightarrow{P}}_{r}\left(x\right)$ defines the placements of the rats. But here's how the $A$ and $C$ parameters are determined:
where $x=\mathrm{0,1},2,...,{Max}_{Iteration}$, and:
Thus, $R$ and $C$ are independent random variables with ranges of [1, 5] and [0, 2], respectively. Over the course of iterations, the parameters $A$ and $C$ lead to better exploration and exploitation.
4.2.2. Fighting with prey
The following equation has been developed to quantitatively define the interaction of rats with prey:
where the revised next position of the rat is defined by ${\overrightarrow{P}}_{i}\left(x+1\right)$. It changes other solutions’ positions and saves the best solution and comparing search agents based on which one is the best. The parameters can be changed to obtain a different number of locations relative to the current position, as indicated in Eqs. (2) and (3). But this idea can also be expanded in an $n$dimensional setting. As a result, the altered value of parameters $A$ and $C$ ensures exploration and exploitation. The best response is saved using the fewest operators via the suggested RSO technique.
5. Binary rat swarm optimizer algorithm for independent dominant metric dimension
Because it maintains a population of solutions and explores a wide region to find the optimum global solution, the Rat Swarm Optimizer Algorithm can solve difficult optimization problems with several locally optimal solutions. This benefit enables a binary variant of the approach to be applied to the dominant independent metric dimension problem. Using position vectors located within the continuous real domain, search agents can navigate the search space in the continuous form of RSOA. By using an $S$shaped transfer function to turn the continuous variable RSOA into a binary one, we may convert it to binary values. Position changes in discrete binary search space necessitate flipping between 0 and 1. The initialization phase makes use of the subsequent equation. Transfer function merits particular consideration and investigation since it plays a significant role in the discrete RSO algorithm:
where $rand(\bullet )$ refers to a random number between 0 and 1. To convert continuous values to binary ones, a transfer function is used. The sigmoid function ($S$) is applied as follows in this study:
where $S$ is the function output and ${x}^{d}$ denotes the continuousvalued location at dimension $d$. To create a binary value, use the equation below:
Table 1Parameter setting with search agents 30 for all algorithms
Algorithms  Parameter name  Value 
BRSOA  Number of generations Control parameter ($R$) Constant parameter $C$ Number of runs  1000 [1, 5] [0, 2] 20 
BWOA  ${a}_{1}$ ${a}_{2}$ Number of runs  Decreasing from 2 to 0 Decreasing from –1 to –2 20 
BPSO  ${C}_{1}$ ${C}_{2}$ Inertia weight ($w$) Number of runs  Increasing linearly from 0.5 to 2.5 Decreasing linearly from 2.5 to 0.5 0.8 20 
BGSA  Gravitational constant Alpha coefficient  100 20 
BGWO  Control parameter ($\overrightarrow{a}$)  [2, 0] 
BMFO  Convergence constant Logarithmic spiral Number of runs  [−1, −2] 0.75 20 
The proposed algorithm deals with the dominant independent resolving set problem as an optimization problem where it searches for the best solution, so each search agent can be represented as a onedimensional vector $SA{binary}_{ij}=({SA}_{i1},\mathrm{}{SA}_{i2},...,\mathrm{}{SA}_{ij})$, for which $SA{binary}_{ij}$ is a binaryvalued position vector if the $j$th element of the vector has a value of 1, it means that vertex $j$ belongs to $B$. If every $v\in V\left(G\right)$ has a distinct representation $r\left(v\rightB)$, then $B$ is an independent dominant resolving set. The value of a binaryvalued position vector is produced by computing the value of the $S$shaped transfer function. In the BRSOA algorithm, when a search agent is not feasible as an independent dominant resolving set, that search agent is repaired by adding a vertex from $V\backslash B$. This repair is applied until that object becomes an independent dominant resolving set.
The algorithm represents each solution (individual) in the population as a string of binary in which 1 means that the independent dominant resolving set will be chosen, then the corresponding value will be “1”, and if the independent dominant resolving set is not selected, then the corresponding value will be “0”. The pseudocode in Algorithm 1.
Table 2Algorithm 1: Pseudocode of BRSOA
Input: The rat population ${P}_{i}(i=\mathrm{1,2},\dots ,n)$ Output: The optimal solution agent 1: Procedure RSOA 2: Initialize the parameters $A$,$C$ and $R$ 3: Evaluate the initial population and select the one with the best fitness value. 4:${P}_{r}\left(x\right)\leftarrow $ The best search agent 5: while ($x\le {Max}_{Iteration}$) do 6: for each search agent do 7: Update the position of current search agent using Eq. (4) 8: Convert each $\overrightarrow{{SA}_{i}}$ into binary using the Sshaped transfer function in $SA{binary}_{ij}$ 9: Calculate the fitness of each $SA{binary}_{ij}$ 10: Update the new position of the search agent using Eq. (7) 11: end for 12: Update parameters $A$,$C$ and $R$ 13: Verify if any search agents exist that extend beyond the specified search space, and then modify them 14: Evaluate the fitness of each search agent 15: Update ${P}_{r}$_{}if a better solution becomes available than the previously optimal option 16: Convert each $\overrightarrow{{SA}_{i}}$ into binary using the Sshaped transfer function in $SA{binary}_{ij}$ 17: Calculate the fitness of each $SA{binary}_{ij}$ 18: Update the new position of the search agent using Eq. (7) 19: Compare the fitness values of each search agent and choose the best candidate 20: Set $x=x+1$ 21: end while 22: return search agent with best fitness value 23: end procedure 
5.1. Experimental results
This section uses theoretically generated graph findings to evaluate the proposed BRSOA. On a path graph, a cycle graph, a fan graph, a ladder graph and a circular ladder graph, the proposed BRSOA is compared to the BWOA, BPSO, BGSA, BGWO and BMFO. The code was implemented in MATLAB 2021b, and the algorithm tests and comparisons were carried out using a Windows 10 Ultimate 64bit operating system with an Intel Core i7 running at 16 GB of RAM, a 1TBHDD + 1TBSSD hard drive. Table 1 displays the parameter setting values.
All algorithms have been run 20 times for each graph and the results are summarized in Tables 36. The tables are organized as follows: The first three columns contain the number of nodes $N$, the number of edges $M$, the independent domination resolving number ${\gamma}_{cr}$, the CPU time ($t$) used to indicate the exactly independent domination resolving number and iteration: The average number of iterations for finishing the algorithms to achieve the best solution, respectively.
It should be noted, based on Table 3, that when computing connected domination resolving number for path graph ${P}_{n}$,$\mathrm{}4\le n\le 19$, then the BRSOA has reached an optimal solution.
Table 3Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for path graph Pn, 4≤n≤19
$N$  $M$  ${\gamma}_{ir}$ $t$ (sec) Iteration  BRSOA  BWOA  BPSO  BGSA  BGWO  BMFO 
4  3  2 16.3 1  2 52.7 2  2 36.4 1  2 24.5 1  2 29.2 1  2 46.7 1  
5  4  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 35.8 2  3 87.3 8  3 51.9 5  3 31.2 3  3 49.1 4  3 73.5 6 
6  5  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 58.4 5  3 132.9 22  3 86.1 13  3 72.8 9  3 83.4 11  3 109.6 18 
7  6  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 83.7 7  4 175.2 35  4 155.9 25  4 126.9 16  4 68.3 19  4 148.1 26 
8  7  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 105.2 10  4 258.3 47  4 236.3 42  4 178.1 28  4 194.9 32  4 215.4 53 
9  8  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 121.8 17  5 389.5 69  5 311.6 50  5 202.8 35  5 243.1 41  5 298.3 59 
10  9  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 156.4 31  5 478.1 78  5 382.2 36  5 274.5 29  5 299.3 56  5 385.9 45 
11  10  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 194.2 22  6 535.7 93  6 447.8 48  6 351.4 56  6 367.9 75  6 457.4 63 
12  11  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 229.1 27  6 589.2 71  6 513.1 39  6 415.9 64  6 406.5 47  6 529.3 82 
13  12  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 283.4 35  7 711.9 105  7 599.5 31  7 501.3 82  7 484.2 63  7 591.7 59 
14  13  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 372.9 45  7 794.4 93  7 678.4 58  7 604.8 69  7 567.9 108  7 673.5 74 
15  14  ${\gamma}_{ir}$ $t$ (sec) Iteration  8 307.2 41  8 881.7 62  8 794.5 84  8 647.3 95  8 685.2 81  8 757.9 103 
16  15  ${\gamma}_{ir}$ $t$ (sec) Iteration  8 356.6 29  8 1013.5 118  8 937.4 95  8 705.9 49  8 779.1 54  8 869.5 73 
17  16  ${\gamma}_{ir}$ $t$ (sec) Iteration  9 328.5 16  9 1183.9 78  9 1021.8 110  9 802.4 56  9 895.3 64  9 957.3 81 
18  17  ${\gamma}_{ir}$ $t$ (sec) Iteration  9 411.8 34  9 1357.2 103  9 1109.3 62  9 896.7 78  9 961.5 89  9 1034.6 88 
19  18  ${\gamma}_{ir}$ $t$ (sec) Iteration  10 443.3 25  10 1562.4 99  10 1239.7 76  10 975.3 62  10 1198.4 70  10 1156.1 91 
Table 4Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for cycle graph Cn, 4≤n≤15, BRSOA has reached an optimal solution
$N$  $M$  ${\gamma}_{ir}$ $t$ (sec) Iteration  BRSOA  BWOA  BPSO  BGSA  BGWO  BMFO 
4  4  2 25.4 1  2 61.8 3  2 42.7 2  2 32.9 1  2 37.2 1  2 43.5 2  
5  5  ${\gamma}_{ir}$ $t$ (sec) Iteration  2 34.8 1  2 79.3 7  2 56.2 3  2 48.2 2  2 54.9 2  2 63.6 3 
6  6  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 61.7 3  3 104.8 19  3 73.8 8  3 59.7 6  3 68.3 9  3 81.4 13 
7  7  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 80.9 6  3 135.6 42  3 97.5 17  3 91.3 15  3 87.1 23  3 108.7 34 
8  8  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 104.2 14  4 176.9 56  4 91.7 31  4 118.2 24  4 128.6 38  4 137.9 48 
9  9  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 129.1 11  4 211.2 73  4 116.4 45  4 173.9 36  4 159.4 24  4 172.1 53 
10  10  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 146.3 26  5 267.9 109  5 174.8 82  5 198.4 61  5 182.1 49  5 207.2 74 
11  11  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 188.9 37  5 341.6 81  5 229.4 89  5 224.3 75  5 216.1 56  5 283.9 103 
12  12  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 207.5 24  6 419.2 134  6 367.8 52  6 268.1 69  6 289.4 48  6 342.6 82 
13  13  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 173.9 32  6 485.7 159  6 442.9 78  6 309.7 83  6 351.9 72  6 407.2 113 
14  14  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 228.6 21  7 562.1 183  7 499.5 93  7 375.2 56  7 412.5 54  7 488.1 66 
15  15  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 294.1 17  7 739.8 201  7 617.3 72  7 476.8 54  7 532.5 69  7 761.4 75 
Table 5Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for friendship graph Frn, 3≤n≤25, BRSOA has reached an optimal solution
$N$  $M$  ${\gamma}_{ir}$ $t$ (sec) Iteration  BRSOA  BWOA  BPSO  BGSA  BGWO  BMFO 
3  3  1 11.9 1  1 29.6 2  1 18.2 1  1 16.3 1  1 22.4 1  1 32.8 2  
5  6  ${\gamma}_{ir}$ $t$ (sec) Iteration  2 16.8 1  2 47.9 7  2 35.8 4  2 28.4 3  2 31.9 2  2 46.7 5 
7  9  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 34.5 6  3 83.1 25  3 72.7 16  3 46.2 7  3 57.8 13  3 89.5 11 
9  12  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 56.7 9  4 139.8 44  4 96.8 35  4 71.5 16  4 81.9 21  4 127.4 32 
11  15  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 95.4 16  5 215.3 59  5 83.9 28  5 107.9 25  5 111.3 38  5 185.9 44 
13  18  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 143.6 28  6 294.1 39  6 154.7 49  6 185.6 42  6 125.4 30  6 248.7 73 
15  21  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 197.1 43  7 376.9 64  7 236.3 73  7 248.4 32  7 221.8 49  7 367.3 57 
17  24  ${\gamma}_{ir}$ $t$ (sec) Iteration  8 262.7 36  8 456.3 75  8 298.2 109  8 293.7 58  8 306.7 74  8 433.9 86 
19  27  ${\gamma}_{ir}$ $t$ (sec) Iteration  9 311.3 21  9 563.9 117  9 374.8 64  9 389.5 70  9 412.5 85  9 524.8 104 
21  30  ${\gamma}_{ir}$ $t$ (sec) Iteration  10 352.9 28  10 657.4 159  10 458.9 86  10 479.3 55  10 464.9 78  10 561.2 123 
23  33  ${\gamma}_{ir}$ $t$ (sec) Iteration  11 388.7 19  11 689.5 208  11 534.2 78  11 515.7 67  11 527.2 61  11 598.5 82 
25  36  ${\gamma}_{ir}$ $t$ (sec) Iteration  12 296.2 14  12 774.8 186  12 592.8 91  12 588.4 45  12 596.3 82  12 634.3 97 
Table 6Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for triangular snake graph Tn, 3≤n≤31, BRSOA has reached an optimal solution.
$N$  $M$  ${\gamma}_{ir}$ $t$ (sec) Iteration  BRSOA  BWOA  BPSO  BGSA  BGWO  BMFO 
3  3  1 10.5 1  1 26.3 4  1 20.8 2  1 19.6 1  1 27.3 1  1 25.2 3  
5  6  ${\gamma}_{ir}$ $t$ (sec) Iteration  2 18.2 1  2 63.7 9  2 46.2 3  2 28.4 2  2 31.9 3  2 46.7 6 
7  9  ${\gamma}_{ir}$ $t$ (sec) Iteration  3 41.4 5  3 99.3 31  3 87.2 15  3 58.9 10  3 74.1 8  3 95.4 19 
9  12  ${\gamma}_{ir}$ $t$ (sec) Iteration  4 59.8 12  4 161.7 38  4 103.5 25  4 41.6 18  4 91.2 21  4 117.5 32 
11  15  ${\gamma}_{ir}$ $t$ (sec) Iteration  5 76.3 16  5 208.1 45  5 174.2 41  5 89.3 27  5 124.9 38  5 154.6 50 
13  18  ${\gamma}_{ir}$ $t$ (sec) Iteration  6 105.9 11  6 246.3 71  6 211.9 62  6 137.6 44  6 192.8 56  6 204.5 78 
15  21  ${\gamma}_{ir}$ $t$ (sec) Iteration  7 189.3 37  7 297.5 93  7 287.1 51  7 201.8 49  7 274.9 74  7 297.3 86 
17  24  ${\gamma}_{ir}$ $t$ (sec) Iteration  8 256.4 24  8 406.2 59  8 358.3 45  8 287.9 76  8 326.2 60  8 382.9 147 
19  27  ${\gamma}_{ir}$ $t$ (sec) Iteration  9 317.8 40  9 485.9 133  9 402.4 49  9 346.3 83  9 398.7 67  9 459.3 95 
21  30  ${\gamma}_{ir}$ $t$ (sec) Iteration  10 383.6 19  10 517.4 106  10 467.2 208  10 398.2 53  10 456.8 104  10 562.4 203 
23  33  ${\gamma}_{ir}$ $t$ (sec) Iteration  11 437.9 13  11 593.5 181  11 538.9 169  11 443.9 62  11 523.5 77  11 623.8 122 
25  36  ${\gamma}_{ir}$ $t$ (sec) Iteration  12 393.2 15  12 649.2 93  12 592.6 103  12 562.8 116  12 587.2 159  12 692.3 181 
27  39  ${\gamma}_{ir}$ $t$ (sec) Iteration  13 431.8 29  13 737.5 84  13 678.2 178  13 642.7 96  13 675.9 113  13 728.9 79 
29  42  ${\gamma}_{ir}$ $t$ (sec) Iteration  14 490.3 21  14 821.9 138  14 731.7 217  14 703.5 71  14 765.8 85  14 784.1 193 
31  45  ${\gamma}_{ir}$ $t$ (sec) Iteration  15 356.9 14  15 879.3 186  15 812.6 204  15 786.9 82  15 807.6 99  15 843.7 161 
6. Comparison
To further demonstrate the excellence of proposed BRSOA, we choose BWOA, BPSO, BGSA, BGWO and BMFO algorithms to conduct experiments under the same conditions and compared the results. The results on graphs are shown in Tables 36, which indicate that proposed BRSOA algorithm, outperforms other algorithms on graphs, reaching 443.3 sec in BRSOA, 1562.4 sec in BWOA, 1239.7 sec in BPSO, 975.3 sec in BGSA, 1198.4 sec in BGWO, 1156.1 sec in BMFO for path graph and 294.3 sec in BRSOA, 739.8 sec in BWOA, 617.3 sec in BPSO, 476.8 sec in BGSA, 532.5 sec in BGWO and 761.4 sec in BMFO for cycle graph and 296.2 sec in BRSOA, 774.8 sec in BWOA, 592.8 sec in BPSO, 588.4 sec in BGSA, 596.3sec in BGWO, and 634.3 sec in BMFO for friendship graph and 356.9 sec in BRSOA, 879.3 sec in BWOA, 812.6 sec in BPSO, 786.9 sec in BGSA, 807.6 sec in BGWO and 843.7 sec in BMFO for triangular snake graph. It proves the correctness and superiority of proposed BRSOA. Figs. 2, 3, 4 and 5 show the superiority of the proposed BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO according to the independent domination resolving number.
Fig. 2The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO
Fig. 3The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO
Fig. 4The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO
Fig. 5The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO
7. Conclusions
In this paper, a binary variant of the basic Rat Swarm Optimizer Algorithm (BRSOA) is adapted for determining the minimum independent domination resolving set of graphs and compared to BWOA, BPSO, BGSA, BGWO and BMFO. Comparisons were performed on the graphs: path graph, cycle graph, friendship graph and triangular snake graph. Experimental results and their analysis confirmed the superiority of the proposed BRSOA for solving the independent 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.
References

T. Mazidah, Dafik, Slamin, I. H. Agustin, and R. Nisviasari, “Resolving independent domination number of some special graphs,” in Journal of Physics: Conference Series, Vol. 1832, No. 1, p. 012022, Mar. 2021, https://doi.org/10.1088/17426596/1832/1/012022

S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discrete Applied Mathematics, Vol. 70, No. 3, pp. 217–229, Oct. 1996, https://doi.org/10.1016/0166218x(95)001062

R. Manjusha and A. S. Kuriakose, “Metric dimension and uncertainty of traversing robots in a network,” International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, Vol. 7, No. 2/3, pp. 1–9, Sep. 2015, https://doi.org/10.5121/jgraphoc.2015.7301

B. Mohamed, “Metric dimension of graphs and its application to robotic navigation,” International Journal of Computer Applications, Vol. 184, No. 15, pp. 1–3, Jun. 2022, https://doi.org/10.5120/ijca2022922090

Z. Beerliova et al., “Network discovery and verification,” IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, pp. 2168–2181, Dec. 2006, https://doi.org/10.1109/jsac.2006.884015

M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir, and S. Ali, “Metric dimension of generalized Möbius ladder and its application to WSN localization,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 24, No. 1, pp. 3–11, Jan. 2020, https://doi.org/10.20965/jaciii.2020.p0003

A. Sebő and E. Tannier, “On metric generators of graphs,” Mathematics of Operations Research, Vol. 29, No. 2, pp. 383–393, May 2004, https://doi.org/10.1287/moor.1030.0070

G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discrete Applied Mathematics, Vol. 105, No. 13, pp. 99–113, Oct. 2000, https://doi.org/10.1016/s0166218x(00)001980

J. L. Hurink and T. Nieberg, “Approximating minimum independent dominating sets in wireless networks,” Information Processing Letters, Vol. 109, No. 2, pp. 155–160, Dec. 2008, https://doi.org/10.1016/j.ipl.2008.09.021

A. H. Karbasi and R. E. Atani, “Application of dominating sets in wireless sensor networks,” International Journal of Security and Its Applications, Vol. 7, No. 4, pp. 185–202, 2013.

B. Das and V. Bharghavan, “Routing in adhoc networks using minimum connected dominating sets,” in ICC’97 – International Conference on Communications, Vol. 1, pp. 376–380, Mar. 2024, https://doi.org/10.1109/icc.1997.605303

B. Das, R. Sivakumar, and V. Bharghavan, “Routing in ad hoc networks using a spine,” in 6th International Conference on Computer Communications and Networks, pp. 34–39, Nov. 2023, https://doi.org/10.1109/icccn.1997.623288

R. Sivakumar, P. Sinha, and V. Bharghavan, “CEDAR: a coreextraction distributed ad hoc routing algorithm,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, pp. 1454–1465, Jan. 1999, https://doi.org/10.1109/49.779926

D. Vukičević and A. Klobučar, “KDominating sets on linear benzenoids and on the infinite hexagonal grid,” Croatica Chemica Acta, Vol. 80, No. 2, pp. 187–191, Jun. 2007.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness. New York: W. H. Freeman and Company, 1979.

S. Imran et al., “Computing the metric dimension of gear graphs,” Symmetry, Vol. 10, No. 6, p. 209, Jun. 2018, https://doi.org/10.3390/sym10060209

B. Mohamed and M. Amin, “The metric dimension of subdivisions of Lilly graph, tadpole graph and special trees,” Applied and Computational Mathematics, Vol. 12, No. 1, pp. 9–14, Mar. 2023, https://doi.org/10.11648/j.acm.20231201.12

M. Imran, M. K. Siddiqui, and R. Naeem, “On the metric dimension of generalized Petersen multigraphs,” IEEE Access, Vol. 6, pp. 74328–74338, Jan. 2018, https://doi.org/10.1109/access.2018.2883556

B. Mohamed and M. Amin, “Domination number and secure resolving sets in cyclic networks,” Applied and Computational Mathematics, Vol. 12, No. 2, pp. 42–45, May 2023, https://doi.org/10.11648/j.acm.20231202.12

P. Singh, S. Sharma, S. K. Sharma, and V. K. Bhat, “Metric dimension and edge metric dimension of windmill graphs,” AIMS Mathematics, Vol. 6, No. 9, pp. 9138–9153, Jan. 2021, https://doi.org/10.3934/math.2021531

S. Nawaz, M. Ali, M. A. Khan, and S. Khan, “Computing metric dimension of power of total graph,” IEEE Access, Vol. 9, pp. 74550–74561, Jan. 2021, https://doi.org/10.1109/access.2021.3072554

A. Khan, G. Haidar, N. Abbas, M. U. I. Khan, A. U. K. Niazi, and A. U. I. Khan, “Metric dimensions of bicyclic graphs,” Mathematics, Vol. 11, No. 4, p. 869, Feb. 2023, https://doi.org/10.3390/math11040869

M. Munir, A. R. Nizami, Z. Iqbal, and H. Saeed, “Metric dimension of the Mobius ladder,” Ars Combinatoria, Vol. 135, pp. 249–256, Oct. 2017.

M. M. Alholi, O. A. Abughneim, and H. A. Ezeh, “Metric dimension of some path related graphs,” Global Journal of Pure and Applied Mathematics, Vol. 3, No. 2, pp. 149–157, 2017.

A. Ahmad, M. Bača, and S. Sultan, “Computing the metric dimension of kayak paddles graph and cycles with chord,” Proyecciones (Antofagasta), Vol. 39, No. 2, pp. 287–300, Apr. 2020, https://doi.org/10.22199/issn.071762792020020018

B. Suganya and S. Arumugam, “Independent resolving sets in graphs,” AKCE International Journal of Graphs and Combinatorics, Vol. 18, No. 2, pp. 106–109, May 2021, https://doi.org/10.1080/09728600.2021.1963643

L. Tang, S. Zhou, J. Chen, and Z. Zhang, “Metric dimension and metric independence number of incidence graphs of symmetric designs,” Discrete Applied Mathematics, Vol. 291, pp. 43–50, Mar. 2021, https://doi.org/10.1016/j.dam.2020.12.001

S. Prabhu, T. Flora, and M. Arulperumjothi, “On independent resolving number of TiO2 [m, n] nanotubes,” Journal of Intelligent and Fuzzy Systems, Vol. 35, No. 6, pp. 6421–6425, Dec. 2018, https://doi.org/10.3233/jifs181314

L. Susilowati, I. Sa’Adah, R. Z. Fauziyyah, A. Erfanian, and Slamin, “The dominant metric dimension of graphs,” Heliyon, Vol. 6, No. 3, p. e03633, Mar. 2020, https://doi.org/10.1016/j.heliyon.2020.e03633

R. P. Adirasari, H. Suprajitno, and L. Susilowati, “The dominant metric dimension of corona product graphs,” Baghdad Science Journal, Vol. 18, No. 2, pp. 0349–349, Jun. 2021, https://doi.org/10.21123/bsj.2021.18.2.0349

Ahmed Mohammed Naji and N. D. Soner, “Resolving connected domination in graphs,” International Journal of Mathematical Combinatorics, Vol. 4, pp. 129–136, Jan. 2015.

J. Kratica, V. KovačevićVujčić, and M. Čangalović, “Computing the metric dimension of graphs by genetic algorithms,” Computational Optimization and Applications, Vol. 44, No. 2, pp. 343–361, Dec. 2007, https://doi.org/10.1007/s1058900791545

D. T. Murdiansyah and Adiwijaya, “Computing the metric dimension of hypercube graphs by particle swarm optimization algorithms,” in Advances in Intelligent Systems and Computing, pp. 171–178, Dec. 2016, https://doi.org/10.1007/9783319512815_18

N. Mladenović, J. Kratica, V. KovačevićVujčić, and M. Čangalović, “Variable neighborhood search for metric dimension and minimal doubly resolving set problems,” European Journal of Operational Research, Vol. 220, No. 2, pp. 328–337, Jul. 2012, https://doi.org/10.1016/j.ejor.2012.02.019

B. Mohamed, L. Mohaisen, and M. Amin, “Binary equilibrium optimization algorithm for computing connected domination metric dimension problem,” Scientific Programming, Vol. 2022, pp. 1–15, Oct. 2022, https://doi.org/10.1155/2022/6076369

B. Mohamed, L. Mohaisen, and M. Amin, “Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization,” Intelligent Automation and Soft Computing, Vol. 36, No. 2, pp. 2349–2361, Jan. 2023, https://doi.org/10.32604/iasc.2023.032930

B. Mohamed and M. Amin, “A hybrid optimization algorithms for solving metric dimension problem,” International Journal on Applications of Graph Theory in wireless Ad Hoc Networks and Sensor Networks, Vol. 15, No. 1/2, pp. 1–10, Jun. 2023, https://doi.org/10.5121/jgraphoc.2023.15201

B. Mohamed, “A comprehensive survey on the metric dimension problem of graphs and its types,” International Journal of Theoretical and Applied Mathematics, Vol. 9, No. 1, pp. 1–5, Jul. 2023, https://doi.org/10.11648/j.ijtam.20230901.11

I. M. Batiha, S. A. Njadat, R. M. Batyha, A. Zraiqat, A. Dababneh, and S. Momani, “Design fractionalorder PID controllers for singlejoint robot arm model,” International Journal of Advances in Soft Computing and its Applications, Vol. 14, No. 2, pp. 97–114, Aug. 2022, https://doi.org/10.15849/ijasca.220720.07

H. M. Paiva, W. S. Keller, and L. G. R. Da Cunha, “Bloodglucose regulation using fractionalorder PID control,” Journal of Control, Automation and Electrical Systems, Vol. 31, No. 1, pp. 1–9, Dec. 2019, https://doi.org/10.1007/s40313019005520

H. AlZoubi, H. Alzaareer, A. Zraiqat, T. Hamadneh, and W. AlMashaleh, “On ruled surfaces of coordinate finite type,” WSEAS Transactions on Mathematics, Vol. 21, pp. 765–769, Nov. 2022, https://doi.org/10.37394/23206.2022.21.87

S. Mirjalili and A. Lewis, “Sshaped versus Vshaped transfer functions for binary Particle Swarm Optimization,” Swarm and Evolutionary Computation, Vol. 9, pp. 1–14, Apr. 2013, https://doi.org/10.1016/j.swevo.2012.09.002

Y. Sharafi, M. A. Khanesar, and M. Teshnehlab, “Discrete binary cat swarm optimization algorithm,” in 2013 3rd IEEE International Conference on Computer, Control and Communication (IC4), pp. 1–6, Sep. 2013, https://doi.org/10.1109/ic4.2013.6653754

S. Mirjalili, S. M. Mirjalili, and X.S. Yang, “Binary bat algorithm,” Neural Computing and Applications, Vol. 25, No. 34, pp. 663–681, Dec. 2013, https://doi.org/10.1007/s0052101315255

S. Sabba and S. Chikhi, “A discrete binary version of bat algorithm for multidimensional knapsack problem,” International Journal of BioInspired Computation, Vol. 6, No. 2, p. 140, Jan. 2014, https://doi.org/10.1504/ijbic.2014.060598
About this article
The authors have not disclosed any funding.
The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.
Iqbal M. Batiha: conceptualization, methodology, software, validation, formal analysis, investigation data curation. Basma Mohamed: conceptualization, methodology, software, validation, formal analysis, investigation, data curation.
The authors declare that they have no conflict of interest.