Approximability of identifying codes and locating-dominating codes

DOI10.1016/J.IPL.2007.02.001MaRDI QIDQ2379937zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsgraph algorithmsidentifying codescombinatorial problemslocating-dominating codes

Mathematics Subject Classification ID

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

Recommendations

• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• The complexity of the identifying code problem in restricted graph classes
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm

Cites work

• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• scientific article; zbMATH DE number 4053685 (Why is no real title available?)
• scientific article; zbMATH DE number 6541785 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• Alarm placement in systems with fault propagation
• Approximation algorithms for combinatorial problems
• Domination and location in acyclic graphs
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Landmarks in graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On Syntactic versus Computational Views of Approximability
• On a new class of codes for identifying vertices in graphs
• On identifying codes
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes

Cited in

(18)

• On Stronger Types of Locating-dominating Codes
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Identifying codes in line graphs
• Network verification via routing table queries
• Identifying and locating-dominating codes in (random) geometric networks
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Identifying codes in hereditary classes of graphs and VC-dimension
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Identifying Codes and Covering Problems
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Identifying and locating-dominating codes on chains and cycles
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Locating-dominating codes in paths
• Complexity results for identifying codes in planar graphs
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379937)