On approximation complexity of metric dimension problem
DOI10.1007/978-3-642-19222-7_15zbMATH Open1326.68149OpenAlexW2034444732MaRDI QIDQ3000502FDOQ3000502
Authors: Mathias Hauptmann, Richard Schmied, Claus Viehmann 
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
Recommendations
approximation algorithmsmetric dimensiondense instancesapproximation lower boundsbounded degree instances
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Title not available (Why is that?)
- Resolvability in graphs and the metric dimension of a graph
- On the Metric Dimension of Cartesian Products of Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Landmarks in graphs
- On the metric dimension of infinite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Metric Generators of Graphs
- The metric dimension of Cayley digraphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Mastermind
- Discrepancies between metric dimension and partition dimension of a connected graph
- Title not available (Why is that?)
- A Combinatory Detection Problem
- Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
- Tight approximability results for test set problems in bioinformatics
- Extremal Graph Theory for Metric Dimension and Diameter
- Graph-Theoretic Concepts in Computer Science
Cited In (8)
- Approximation complexity of metric dimension problem
- Title not available (Why is that?)
- On optimal approximability results for computing the strong metric dimension
- Variable neighborhood search for metric dimension and minimal doubly resolving set problems
- A note on the complexity of \(k\)\textsc{-metric dimension}
- On the Complexity of Metric Dimension
- On approximation algorithm for the edge metric dimension problem
- On the complexity of computing the Hausdorff distance
This page was built for publication: On approximation complexity of metric dimension problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000502)
