Approximability of identifying codes and locating-dominating codes
From MaRDI portal
Publication:2379937
DOI10.1016/J.IPL.2007.02.001zbMATH Open1183.94059OpenAlexW2145297213MaRDI QIDQ2379937FDOQ2379937
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
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
approximation algorithmsgraph algorithmsidentifying codescombinatorial problemslocating-dominating codes
Cites Work
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- Optimization, approximation, and complexity classes
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On identifying codes
- Title not available (Why is that?)
- On a new class of codes for identifying vertices in graphs
- Landmarks in graphs
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Title not available (Why is that?)
- Domination and location in acyclic graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On Syntactic versus Computational Views of Approximability
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Alarm placement in systems with fault propagation
Cited In (18)
- 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
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- On Stronger Types of Locating-dominating Codes
- Identifying Codes and Covering Problems
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in 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
- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Network verification via routing table queries
- Identifying and locating-dominating codes on chains and cycles
- Complexity results for identifying codes in planar graphs
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Locating-dominating codes in paths
- 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)
