الفهرس 
Chapter 1: Resolvability of Graphs and Types of Metric DimensionsOnly 14 pages are availabe for public view
 |  | from | 144 |  |  |
| | | from | 144 | | |
Abstract
A set of vertices B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the vertices in B. The minimum resolving set of G is called locating set or metric basis of G. The cardinality number of the metric basis of G is called locating number or metric dimension of 𝐺.
The problem of determining the metric dimension of graphs arises in several applications such as robot navigation, locating an intruder in a network, network discovery and verification, wireless sensor network localization, telecommunication, geographical routing protocol, pattern recognition, image processing, combinatorial optimization and pharmaceutical chemistry.
Navigation of a robot assumes that there is neither the concept of direction nor that of visibility. But the navigating agent can send a signal to find out how far it is from each set of fixed landmarks. The robot navigation problem is to compute the minimum number of landmarks required, and where they should be placed so that the robot can always determine its location. Navigation of a robot can be studied in a space represented by a graph. The metric basis of the graph is the set of nodes where the landmarks are positioned and the number of landmarks is the metric dimension of the graph.
Locating an intruder of a computer network such as fault in the network, spoiled device and unauthorized connection can be solved in graph-based representation of a computer network, where each vertex may be seen as a possible location for an intruder. The locating set of the graph uniquely recognizes each vertex of the graph so that it controls such a possible intruder.
In Chemistry, a usual representation for the structure of a chemical compound is a labeled graph where the vertex and edge labels specify the atom and bond types, respectively. Metric dimension allow to obtain unique representations for chemical substances. In particular, they were used in pharmaceutical research for discovering patterns common to a variety of drugs.
A metric basis B of G is connected if the subgraph ̅induced by B is a nontrivial connected subgraph of G. The cardinality number of the connected metric basis is the connected metric dimension of G.
Summary
ix
A metric basis B of G = (V, E) is a dominating if every vertex of V⧵B has at least one neighbor that belongs to . The cardinality of the dominating metric basis B is the dominating metric dimension of G.
If a metric basis B of G is connected and dominated, then the cardinality number of B is the connected dominated metric dimension of G. Connected dominated metric dimension of graphs has its applications in networks information exchange and defining virtual backbone architecture in Ad-Hoc wireless networks.
The metric dimension, the connected metric dimension, the dominating metric dimension and the connected dominated metric dimension of several graphs are analytically computed in the literature. The other hand, only the metric dimension of graphs is computed heuristically. Moreover, a few algorithms: genetic algorithm, particle swarm optimization algorithm, and variable neighborhood search algorithm are adapted to compute the metric dimension of graphs.
The aim of this research is the development of algorithms to compute metric dimension, the connected metric dimension, the dominating metric dimension and the connected dominated metric dimension of graphs as major interest in computer science. Also, for all types of metric dimension, several classes of graphs are analytically determined for the purpose of using them in experimental results.
The main contributions of the thesis are:
Proposing a hybrid Slime Mould Algorithm with Simulated Annealing (SMA-SA) for determining the metric dimension of graphs.
Proposing a binary enhanced Harris Hawk Optimization (BEHHO) algorithm for solving the connected metric dimension problem.
Proposing a binary version of the Archimedes optimization algorithm (BAOA) to solve the dominant metric dimension problem.
Proposing a binary variant of the basic equilibrium optimization algorithm (BEOA) for solving the connected domination metric dimension problem.
Application of metric dimension of graphs to robotic navigation.
Summary
x
Computing theoretically the metric dimension of alternate snake family of graphs
Computing theoretically the metric dimension of subdivisions of Lilly graph, Tadpole graph and special trees.
Computing theoretically the connected metric dimension of the class of ladder graphs.
The content is divided into seven chapters. Chapter one introduces the background, definitions, and terminology necessary to read the following chapters. Also, it provides the aims and organization of the thesis.
Chapter two reviews metaheuristic algorithms that adapted for solving the metric dimension problem in the literature. Additionally, it reviews analytical results of metric dimension, connected metric dimension, dominating metric dimension and connected dominated metric dimension.
Chapter three proposes a hybrid Slime Mould Algorithm with Simulated Annealing (SMA_SA) for solving the metric dimension problem. SMA is combined with SA as a global optimizer to enhance its performance and to flee from local optima. The SMA_SA algorithm is compared to SMA algorithm, SA algorithm and other relevant literature: Variable neighborhood search (VNS) algorithm, genetic algorithm (GA) and particle swarm optimization (PSO) algorithm. Computational results show that SMA_SA outperform them. Also, this chapter computes analytically the metric dimension for the family of alternate snake graphs and subdivisions of some special graphs.
Chapter four proposes a Binary Enhanced Harris Hawks Optimization algorithm (BEHHO) that combines classical HHO with opposition-based learning (OBL) and chaotic local search (CLS) to overcome the limitation of HHO. OBL is used to enhance the exploration ability via random initializing process and updating solutions. CLS is used to boost the efficiency of local optimization and to enhance the capability of exploitation in the neighborhood area and accelerate convergence curve. The core exploratory and exploitative processes of the BEHHO are equipped with an S-shaped transfer function to convert the continuous variable into a binary one and adapted for solving the connected metric dimension problem. Experimental results revealed that the BEHHO provided competitive and superior performance in terms of finding
Summary
xi
best solution (known connected metric dimension) and CPU-time compared to classical Harris Hawk Optimization (BHHO), a binary version of opposition-based learning Harris Hawk Optimization (BOHHO) and binary version of chaotic local search Harris Hawk Optimization (BCHHO) algorithms. Also, this chapter computes analytically the metric dimension of the class of ladder graphs. Specifically, ladder graph, circular ladder graph, open ladder graph, triangular ladder graph, open triangular ladder graph, slanting ladder graph and open diagonal ladder graph. Chapter five proposes the Binary Archimedes Optimization Algorithm (BAOA) for computing the dominant metric dimension. BAOA is evaluated against the binary whale optimization algorithm (BWOA) and binary particle swarm optimization (BPSO) and found considerably effective in computing the dominant metric dimension, Chapter six proposes Binary Equilibrium Optimization Algorithm (BEOA) for computing the connected domination metric dimension. BEOA is compared to the state-of- art algorithms including binary Slime Mould Optimizer (BSMO), the binary Grasshopper Optimizer (BGO), the binary Artificial Ecosystem Optimizer (BAEO), the binary Elephant Herding Optimizer (BEHO), the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer (BPSO), and the binary Whale Optimizer (BWO). Computational results show that the proposed BEOA algorithm outperforms them. Finally Chapter seven investigates the metric dimension in terms of contraction and bijection when a robot is navigating a network modeled by the (2,1)C4 -snake graph, 2Δ2–snake graph and 3C4–snake graph.