Approximation complexity of metric dimension problem

DOI10.1016/j.jda.2011.12.010zbMath1247.68100WikidataQ56551563 ScholiaQ56551563MaRDI QIDQ450564

Mathias Hauptmann, Richard Schmied, Claus Viehmann

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.010

zbMATH Keywords

approximation algorithms; dense instances; metric dimension; approximation lower bounds; bounded degree instances

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Vertex identification in trees, Resolvability of Hamming Graphs, Sharp bound on the truncated metric dimension of trees, Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, A note on the complexity of \(k\)\textsc{-metric dimension}, The fault‐tolerant beacon set of hexagonal Möbius ladder network, A linear time algorithm for metric dimension of cactus block graphs, Complexity of metric dimension on planar graphs, The (weighted) metric dimension of graphs: hard and easy cases, On optimal approximability results for computing the strong metric dimension, Approximation for the minimum cost doubly resolving set problem, The weighted 2-metric dimension of trees in the non-landmarks model, Metric dimension of critical Galton-Watson trees and linear preferential attachment trees, Computation of edge resolvability of benzenoid tripod structure, The locating number of hexagonal Möbius ladder network, On the robustness of the metric dimension of grid graphs to adding a single edge, On approximation algorithm for the edge metric dimension problem, Low-dimensional representation of genomic sequences, Computing the metric dimension for chain graphs, On the limiting distribution of the metric dimension for random forests, The \(k\)-metric dimension, Levenshtein graphs: resolvability, automorphisms \& determining sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mastermind
• The metric dimension of Cayley digraphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Resolvability in graphs and the metric dimension of a graph
• Complexity of approximating bounded variants of optimization problems
• Tight approximability results for test set problems in bioinformatics
• Discrepancies between metric dimension and partition dimension of a connected graph
• Landmarks in graphs
• On the Metric Dimension of Infinite Graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Extremal Graph Theory for Metric Dimension and Diameter
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• On Metric Generators of Graphs
• A Combinatory Detection Problem
• Algorithms and Computation