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.004zbMath1325.05166OpenAlexW1973765739MaRDI QIDQ2018540
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (15)
More results on the complexity of identifying problems in graphs ⋮ Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ On three domination-based identification problems in block graphs ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Operads of finite posets ⋮ On the minimum size of an identifying code over all orientations of a graph ⋮ Locating-Domination and Identification ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices ⋮ Locating-dominating sets of functigraphs ⋮ Bounding the trace function of a hypergraph with applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Dominating sets for split and bipartite graphs
- On separating systems
- Domination in convex and chordal bipartite graphs
- Discriminating codes in (bipartite) planar graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Minimal identifying codes in trees and planar graphs with large girth
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Dominating sets in perfect graphs
- Unit disk graphs
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Approximation algorithms for the test cover problem
- Some APX-completeness results for cubic graphs
- Domination and total domination on asteroidal triple-free graphs
- Approximation hardness of edge dominating set problems
- Approximability of identifying codes and locating-dominating codes
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Complexity of the Identifying Code Problem in Restricted Graph Classes
- Complexity results for identifying codes in planar graphs
- Identifying and Locating–Dominating Codes in (Random) Geometric Networks
- Identifying Codes and Covering Problems
- Domination in permutation graphs
- Domination and location in acyclic graphs
- Edge Dominating Sets in Graphs
- Dominating Sets in Chordal Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Graph Classes: A Survey
- Structure in Approximation Classes
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- On a new class of codes for identifying vertices in graphs
- How complex are random graphs in first order logic?
- Identifying Codes in Line Graphs
- Approximation and Online Algorithms
This page was built for publication: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
