On the Complexity of Metric Dimension

DOI10.1007/978-3-642-33090-2_37zbMath1365.68277arXiv1107.2256OpenAlexW2157537934WikidataQ56551549 ScholiaQ56551549MaRDI QIDQ2912859

Erik Jan van Leeuwen, Olli Pottonen, Maria J. Serna, Josep Diaz

Publication date: 25 September 2012

Published in: Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.2256

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A linear time algorithm for metric dimension of cactus block graphs, Uniquely identifying the edges of a graph: the edge metric dimension, On the strong Roman domination number of graphs, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity, The \(k\)-metric dimension, Metric Dimension for Amalgamations of Graphs, Metric Dimension of Bounded Width Graphs, Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, The metric dimension of the zero-divisor graph of a matrix semiring, A note on the complexity of \(k\)\textsc{-metric dimension}, Approximation for the minimum cost doubly resolving set problem, Extending the metric dimension to graphs with missing edges, Computing the \(k\)-metric dimension of graphs, Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension, The (weighted) metric dimension of graphs: hard and easy cases, On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs, Computing the metric dimension of a graph from primary subgraphs, Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds., The weighted 2-metric dimension of trees in the non-landmarks model, Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs, THE METRIC DIMENSION OF THE ANNIHILATING-IDEAL GRAPH OF A FINITE COMMUTATIVE RING, Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs, On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs, Computing the metric dimension for chain graphs, On the limiting distribution of the metric dimension for random forests, Metric Dimension of Bounded Tree-length Graphs