On approximation complexity of metric dimension problem

DOI10.1007/978-3-642-19222-7_15MaRDI QIDQ3000502zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsmetric dimensiondense instancesapproximation lower boundsbounded degree instances

Mathematics Subject Classification ID

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

Recommendations

• Approximation complexity of metric dimension problem
• On the Complexity of Metric Dimension
• On optimal approximability results for computing the strong metric dimension
• Complexity of metric dimension on planar graphs
• On approximation algorithm for the edge metric dimension problem

Cites work

• scientific article; zbMATH DE number 5844285 (Why is no real title available?)
• scientific article; zbMATH DE number 4070954 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1163714 (Why is no real title available?)
• scientific article; zbMATH DE number 1875415 (Why is no real title available?)
• A Combinatory Detection Problem
• Approximation hardness of dominating set problems in bounded degree graphs
• Discrepancies between metric dimension and partition dimension of a connected graph
• Extremal Graph Theory for Metric Dimension and Diameter
• Graph-Theoretic Concepts in Computer Science
• Landmarks in graphs
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Mastermind
• On Metric Generators of Graphs
• On the Metric Dimension of Cartesian Products of Graphs
• On the metric dimension of infinite graphs
• Resolvability in graphs and the metric dimension of a graph
• The metric dimension of Cayley digraphs
• Tight approximability results for test set problems in bioinformatics

Cited in

(9)

• Variable neighborhood search for metric dimension and minimal doubly resolving set problems
• On approximation algorithm for the edge metric dimension problem
• A note on the complexity of \(k\)\textsc{-metric dimension}
• scientific article; zbMATH DE number 6310892 (Why is no real title available?)
• On optimal approximability results for computing the strong metric dimension
• On the complexity of computing the Hausdorff distance
• Approximation complexity of metric dimension problem
• On the Complexity of Metric Dimension
• On approximation algorithm for the edge metric dimension problem

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)