Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
zbMATH Open1277.68088MaRDI QIDQ2867320FDOQ2867320
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
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
combinatorial optimizationapproximation algorithmsgraph algorithmsfault toleranceidentifying codesdomination problemsapproximation hardnesslocating-dominating codes
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)
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
- The \textsc{Red-Blue Separation} problem on graphs
- Identifying codes in line graphs
- Algorithms and complexity for metric dimension and location-domination on interval and permutation 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
- Locating-dominating sets: from graphs to oriented graphs
- Identifying codes in vertex-transitive graphs and strongly regular 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)
