Approximation complexity of metric dimension problem

DOI10.1016/J.JDA.2011.12.010zbMATH Open1247.68100DBLPjournals/jda/HauptmannSV12OpenAlexW2174493139WikidataQ56551563 ScholiaQ56551563MaRDI QIDQ450564FDOQ450564

Authors: Mathias Hauptmann, Richard Schmied, Claus Viehmann 

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.010

Recommendations

• On approximation complexity of metric dimension problem
• On the Complexity of Metric Dimension
• On optimal approximability results for computing the strong metric dimension
• On approximation algorithm for the edge metric dimension problem
• Complexity of approximation problems
• A note on the complexity of \(k\)\textsc{-metric dimension}
• scientific article; zbMATH DE number 1206797
• Complexity of metric dimension on planar graphs
• A hardness of approximation result in metric geometry
• On complexity of metric spaces

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) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• Complexity of approximating bounded variants of optimization problems
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• 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
• Algorithms and Computation

Cited In (28)

• A polynomial time computable metric between points sets
• The weighted 2-metric dimension of trees in the non-landmarks model
• A linear time algorithm for metric dimension of cactus block graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• On optimal approximability results for computing the strong metric dimension
• Complexity of metric dimension on planar graphs
• The fault‐tolerant beacon set of hexagonal Möbius ladder network
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• The \(k\)-metric dimension
• The locating number of hexagonal Möbius ladder network
• The (weighted) metric dimension of graphs: hard and easy cases
• Sharp bound on the truncated metric dimension of trees
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• A note on the complexity of \(k\)\textsc{-metric dimension}
• On the limiting distribution of the metric dimension for random forests
• Approximation for the minimum cost doubly resolving set problem
• Resolvability of Hamming graphs
• Computation of edge resolvability of benzenoid tripod structure
• Source detection on graphs
• Low-dimensional representation of genomic sequences
• On approximation complexity of metric dimension problem
• Vertex identification in trees
• Levenshtein graphs: resolvability, automorphisms \& determining sets
• On the Complexity of Metric Dimension
• On approximation algorithm for the edge metric dimension problem
• On approximation algorithm for the edge metric dimension problem
• Computing the metric dimension for chain graphs
• On the complexity of computing the Hausdorff distance

This page was built for publication: 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 Q450564)