On Approximation Complexity of Metric Dimension Problem
From MaRDI portal
Publication:3000502
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
approximation algorithmsdense instancesmetric dimensionapproximation lower boundsbounded degree instances
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (1)
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