A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types

摘要

Consider a robot that is navigating a graph-based environment and trying to figure out where it is at the moment. It can send a signal to determine how far away it is from every set of fixed landmarks. We address the problem of finding exactly the minimum number of landmarks required and their perfect placement to make sure the robot can always locate itself. The graph's metric dimension is the quantity of landmarks, and the graph's metric basis is the set of nodes on which they are distributed. The metric dimension of a graph is the smallest set of nodes needed to uniquely identify every other node using the shortest path distances. Optimization, network theory, navigation, pattern recognition, image processing, locating the origin of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces are a few examples of applications for metric dimension. Also, Due to its many and varied applications in fields like social sciences, communications networks, algorithmic designs, and others, the study of dominance is the kind of metric dimension that is developing at the fastest rate. This survey provides a self-contained introduction to the metric dimension and an overview of several metric dimension results and applications. We also present algorithms for computing the metric dimension of families of graphs.