Approximation complexity of metric dimension problem

DOI10.1016/j.jda.2011.12.010zbMath1247.68100OpenAlexW2174493139WikidataQ56551563 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 algorithmsdense instancesmetric dimensionapproximation lower boundsbounded degree instances

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

A linear time algorithm for metric dimension of cactus block graphs ⋮ Vertex identification in trees ⋮ On the robustness of the metric dimension of grid graphs to adding a single edge ⋮ Complexity of metric dimension on planar graphs ⋮ The \(k\)-metric dimension ⋮ 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} ⋮ Approximation for the minimum cost doubly resolving set problem ⋮ The fault‐tolerant beacon set of hexagonal Möbius ladder network ⋮ Levenshtein graphs: resolvability, automorphisms \& determining sets ⋮ Resolvability of Hamming Graphs ⋮ On approximation algorithm for the edge metric dimension problem ⋮ The (weighted) metric dimension of graphs: hard and easy cases ⋮ On optimal approximability results for computing the strong metric dimension ⋮ 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 ⋮ Low-dimensional representation of genomic sequences ⋮ Computing the metric dimension for chain graphs ⋮ On the limiting distribution of the metric dimension for random forests

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

This page was built for publication: Approximation complexity of metric dimension problem