Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs

MaRDI QIDQ2867320zbMATH OpenFDO

Authors Sylvain Gravier, Ralf Klasing, Julien Moncel

Publication date 11 December 2013

Published in Algorithmic Operations Research (Search for Journal in Brave)

Full work available at URL http://journals.hil.unb.ca/index.php/AOR/article/view/2808

zbMATH Keywords

combinatorial optimizationapproximation algorithmsgraph algorithmsfault toleranceidentifying codesdomination problemsapproximation hardnesslocating-dominating codes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory to circuits and networks (94C15) Other types of codes (94B60)

Recommendations

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

Cited in

(24)

• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
• Identifying and locating-dominating codes in (random) geometric networks
• Identifying codes in hereditary classes of graphs and VC-dimension
• On Stronger Types of Locating-dominating Codes
• Identifying Codes and Covering Problems
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Solving Two Conjectures regarding Codes for Location in Circulant Graphs
• Bounds and extremal graphs for total dominating identifying codes
• Locating-domination and identification
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• The \textsc{Red-Blue Separation} problem on graphs
• Identifying codes in line graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Network verification via routing table queries
• Identifying and locating-dominating codes on chains and cycles
• The compared costs of domination location-domination and identification
• Complexity results for identifying codes in planar graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Approximability of identifying codes and locating-dominating codes
• Identifying codes in vertex-transitive graphs and strongly regular graphs
• Locating-dominating sets: from graphs to oriented graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Locating-dominating codes in paths

This page was built for publication: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs

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