On Approximation Complexity of Metric Dimension Problem

DOI10.1007/978-3-642-19222-7_15zbMath1326.68149OpenAlexW2034444732MaRDI QIDQ3000502

Mathias Hauptmann, Claus Viehmann, Richard Schmied

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_15

zbMATH Keywords

approximation algorithmsdense instancesmetric dimensionapproximation lower boundsbounded degree instances

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Variable neighborhood search for metric dimension and minimal doubly resolving set problems

Cites Work

• 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
• 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
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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