Advances in Metric Dimension: Variants, Algorithms, and Open Challenges

Abstract

The metric dimension of a graph is an elementary notion of graph theory measuring the minimum number of ref-erence points (a resolving set) needed to label uniquely all vertices based on their distance to the points. The review of the subject elaborates on the theoretical underpinning of the metric di-mension, its central versions (local, strong, fault-tolerant, and edge metric dimensions), and algorithmic properties, such as NP-hardness and approximations. Besides, we high-light several applications of network verification, robotics, chemistry, biology, and cybersecurity.  Open problems and directions for future research are also discussed, noting the growing importance of metric dimension in both theoretical and applied fields.