Approximation complexity of metric dimension problem

DOI10.1016/J.JDA.2011.12.010MaRDI QIDQ450564zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

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 3494441 (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
• Algorithms and Computation
• Approximation hardness of dominating set problems in bounded degree graphs
• Complexity of approximating bounded variants of optimization problems
• Discrepancies between metric dimension and partition dimension of a connected graph
• Extremal Graph Theory for Metric Dimension and Diameter
• 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

(28)

• On the complexity of computing the Hausdorff distance
• 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
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• The \(k\)-metric dimension
• The (weighted) metric dimension of graphs: hard and easy cases
• The fault‐tolerant beacon set of hexagonal Möbius ladder network
• The locating number of hexagonal Möbius ladder network
• 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
• Computation of edge resolvability of benzenoid tripod structure
• Resolvability of Hamming graphs
• Low-dimensional representation of genomic sequences
• Source detection on graphs
• 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

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)