Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
From MaRDI portal
Publication:2018540
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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)
Recommendations
- The complexity of the identifying code problem in restricted graph classes
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- Approximability of identifying codes and locating-dominating codes
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Complexity results for identifying codes in planar graphs
Cites work
- scientific article; zbMATH DE number 3161569 (Why is no real title available?)
- scientific article; zbMATH DE number 3906528 (Why is no real title available?)
- scientific article; zbMATH DE number 4053685 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- Approximability of identifying codes and locating-dominating codes
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for combinatorial problems
- Approximation algorithms for the test cover problem
- Approximation and Online Algorithms
- Approximation hardness of dominating set problems in bounded degree graphs
- Approximation hardness of edge dominating set problems
- Complexity results for identifying codes in planar graphs
- Discriminating codes in (bipartite) planar graphs
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Dominating Sets in Chordal Graphs
- Dominating sets for split and bipartite graphs
- Dominating sets in perfect graphs
- Domination and location in acyclic graphs
- Domination and total domination on asteroidal triple-free graphs
- Domination in convex and chordal bipartite graphs
- Domination in permutation graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Edge Dominating Sets in Graphs
- Graph Classes: A Survey
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- How complex are random graphs in first order logic?
- Identifying Codes and Covering Problems
- Identifying and locating-dominating codes in (random) geometric networks
- Identifying codes in line graphs
- Minimal identifying codes in trees and planar graphs with large girth
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Monadic second-order evaluations on tree-decomposable graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On a new class of codes for identifying vertices in graphs
- On separating systems
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Structure in Approximation Classes
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The complexity of the identifying code problem in restricted graph classes
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Unit disk graphs
Cited in
(27)- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Locating-domination and identification
- Approximability of identifying codes and locating-dominating codes
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Linear-time algorithms for three domination-based separation problems in block graphs
- Bounding the trace function of a hypergraph with applications
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
- The complexity of the identifying code problem in restricted graph classes
- On Iiro Honkala's contributions to identifying codes
- Identifying and locating-dominating codes in (random) geometric networks
- On the minimum size of an identifying code over all orientations of a graph
- 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
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Identifying Codes and Covering Problems
- Locating-dominating sets of functigraphs
- Some links between identifying codes and separating, dominating and total dominating sets in graphs
- On three domination-based identification problems in block graphs
- More results on the complexity of identifying problems in graphs
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Operads of finite posets
- Discriminating codes in bipartite graphs
- On three domination-based identification problems in block graphs
This page was built for publication: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018540)
