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

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