Approximability of identifying codes and locating-dominating codes

DOI10.1016/j.ipl.2007.02.001zbMath1183.94059OpenAlexW2145297213MaRDI QIDQ2379937

Jukka Suomela

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.02.001

zbMATH Keywords

combinatorial problemsgraph algorithmsapproximation algorithmsidentifying codeslocating-dominating codes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial codes (94B25)

Related Items (11)

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ Identifying Codes in Line Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Complexity results for identifying codes in planar graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-dominating codes in paths ⋮ Network verification via routing table queries ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Alarm placement in systems with fault propagation
• Landmarks in graphs
• Domination and location in acyclic graphs
• A Greedy Heuristic for the Set-Covering Problem
• On Syntactic versus Computational Views of Approximability
• On the hardness of approximating minimization problems
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On a new class of codes for identifying vertices in graphs
• Identifying and locating-dominating codes: NP-completeness results for directed graphs

This page was built for publication: Approximability of identifying codes and locating-dominating codes