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