The (weighted) metric dimension of graphs: hard and easy cases

DOI10.1007/s00453-014-9896-2zbMath1320.05030OpenAlexW2103905945MaRDI QIDQ494798

Gerhard J. Woeginger, Asaf Levin, Leah Epstein

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://research.tue.nl/nl/publications/the-weighted-metric-dimension-of-graphs--hard-and-easy-cases(f86db641-15c6-46a0-a1fc-6a69fd710049).html

zbMATH Keywords

graph algorithmsmetric dimensiongraph classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (28)

Parameterized Complexity of Geodetic Set ⋮ Complexity of metric dimension on planar graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ The \(k\)-metric dimension ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters ⋮ Monitoring edge-geodetic sets in graphs ⋮ On the metric dimension of bipartite graphs ⋮ On the geodesic identification of vertices in convex plane graphs ⋮ 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 ⋮ Monitoring the edges of a graph using distances ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Comparing the metric and strong dimensions of graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Edge metric dimension of some generalized Petersen graphs ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Metric dimension parameterized by treewidth ⋮ Metric dimension of maximal outerplanar graphs ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem ⋮ 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 ⋮ \(l\)-clique metric dimension of graphs ⋮ Hardness of metric dimension in graphs of constant treewidth ⋮ Parameterized Complexity of Geodetic Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation complexity of metric dimension problem
• Mastermind
• On the order of uniprimitive permutation groups
• Resolvability in graphs and the metric dimension of a graph
• Landmarks in graphs
• On the Complexity of Metric Dimension
• On the Metric Dimension of Cartesian Products of Graphs
• A Linear Recognition Algorithm for Cographs
• Metric bases in digital geometry
• The NP-completeness column: an ongoing guide
• On Metric Generators of Graphs

This page was built for publication: The (weighted) metric dimension of graphs: hard and easy cases