Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
From MaRDI portal
Publication:2018540
DOI10.1016/J.JDA.2014.08.004zbMATH Open1325.05166OpenAlexW1973765739MaRDI QIDQ2018540FDOQ2018540
Publication date: 24 March 2015
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2014.08.004
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
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)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Graph Classes: A Survey
- Unit disk graphs
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Approximation algorithms for the test cover problem
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Complexity results for identifying codes in planar graphs
- Approximation algorithms for NP-complete problems on planar graphs
- On a new class of codes for identifying vertices in graphs
- Title not available (Why is that?)
- Identifying Codes in Line Graphs
- Minimal identifying codes in trees and planar graphs with large girth
- Title not available (Why is that?)
- Structure in Approximation Classes
- Dominating sets in perfect graphs
- Dominating sets for split and bipartite graphs
- Domination in convex and chordal bipartite graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Domination, independent domination, and duality in strongly chordal graphs
- Edge Dominating Sets in Graphs
- Domination and total domination on asteroidal triple-free graphs
- Title not available (Why is that?)
- Dominating Sets in Chordal Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Domination and location in acyclic graphs
- On separating systems
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Monadic second-order evaluations on tree-decomposable graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Domination in permutation graphs
- Approximation and Online Algorithms
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- Identifying and locating-dominating codes in (random) geometric networks
- How complex are random graphs in first order logic?
- Identifying Codes and Covering Problems
- Approximability of identifying codes and locating-dominating codes
- Approximation hardness of edge dominating set problems
- Discriminating codes in (bipartite) planar graphs
- The Complexity of the Identifying Code Problem in Restricted Graph Classes
Cited In (21)
- More results on the complexity of identifying problems in graphs
- Parameterized and approximation complexity of \textsc{Partial VC Dimension}
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Identifying and locating-dominating codes in (random) geometric networks
- Identifying Codes and Covering Problems
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On three domination-based identification problems in block graphs
- On Iiro Honkala's contributions to identifying codes
- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Operads of finite posets
- On the minimum size of an identifying code over all orientations of a graph
- Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
- Locating-Domination and Identification
- Locating-dominating sets of functigraphs
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Bounding the trace function of a hypergraph with applications
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- 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)
