On the Complexity of Metric Dimension

DOI10.1007/978-3-642-33090-2_37MaRDI QIDQ2912859zbMATH OpenOpenAlexWikidataFDO

Authors Olli Pottonen, Erik Jan van Leeuwen, J. Díaz, Maria Serna

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

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

Abstract: The metric dimension of a graph $G$ is the size of a smallest subset $LsubseteqV(G)$ such that for any $x,yinV(G)$ with $xot=y$ there is a $zinL$ such that the graph distance between $x$ and $z$ differs from the graph distance between $y$ and $z$. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree $6$ is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.

Recommendations

• On complexity of metric spaces
• A note on the complexity of \(k\)\textsc{-metric dimension}
• On approximation complexity of metric dimension problem
• Approximation complexity of metric dimension problem
• Complexity of metric dimension on planar graphs
• The Complexity of Metric Realization
• Computational complexity on computable metric spaces
• scientific article; zbMATH DE number 4182360
• scientific article; zbMATH DE number 90608
• scientific article; zbMATH DE number 3962735

Cited in

(47)

• Uniquely identifying the edges of a graph: the edge metric dimension
• Computing the \(k\)-metric dimension of graphs
• The weighted 2-metric dimension of trees in the non-landmarks model
• Metric dimension parameterized by treewidth
• Metric dimension of maximal outerplanar graphs
• Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs
• Alternative parameterizations of \textsc{Metric Dimension}
• Computing the metric dimension for chain graphs
• On the limiting distribution of the metric dimension for random forests
• 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
• On the metric dimension of HDN
• Landmarks in graphs
• A linear time algorithm for metric dimension of cactus block graphs
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Metric dimension of directed graphs
• Metric dimension parameterized by max leaf number
• Metric dimension for amalgamations of graphs
• Metric dimension of bounded width graphs
• On approximation complexity of metric dimension problem
• Complexity of metric dimension on planar graphs
• Approximation complexity of metric dimension problem
• 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
• The metric dimension of the annihilating-ideal graph of a finite commutative ring
• Amorphic complexity can take any nonnegative value in general metric spaces
• 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
• The adjacency dimension of graphs
• On optimal approximability results for computing the strong metric dimension
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• The (weighted) metric dimension of graphs: hard and easy cases
• Hyperbolic Dimension and Decomposition Complexity
• Metric Dimension of Bounded Tree-length Graphs
• scientific article; zbMATH DE number 7650213 (Why is no real title available?)
• 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
• On finding the best and worst orientations for the metric dimension
• A note on the complexity of \(k\)\textsc{-metric dimension}
• Hardness of metric dimension in graphs of constant treewidth
• Metric Dimension Parameterized by Treewidth in Chordal Graphs
• Mixed metric dimension over (edge) corona products
• Metric dimension of ultrametric spaces
• On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
• Approximation for the minimum cost doubly resolving set problem
• Extending the metric dimension to graphs with missing edges

This page was built for publication: On the Complexity of Metric Dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912859)