Approximation complexity of Metric Dimension problem

2011/12/08 by Mathias Hauptmann, Richard Schmied, Claus Viehmann · 5 citations
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Bounded function #Chordal graph #Combinatorics #DTIME #Degree (music) #Dimension (graph theory) #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Mathematical analysis #Mathematics #Metric (unit) #Metric dimension #Turing machine #Vertex (graph theory) #Vertex cover #graph theory and CDMA systems

paper · pdf · doi:10.1016/j.jda.2011.12.010

openalex publication_date 2011/12/08 · crossref created 2011/12/08 · crossref issued 2012/07/01 · crossref published 2012/07/01 · crossref published-print 2012/07/01 · crossref deposited 2019/06/20 · openalex created_date 2025/10/10 · crossref indexed 2026/05/27 · openalex updated_date 2026/08/02

Citations

• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Infinite Graphs

Cited by

• On the Complexity of Metric Dimension
• On the Parameterized and Approximation Hardness of Metric Dimension
• The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
• Computing the metric dimension for chain graphs
• Metric dimension (graph theory) [wikipedia]