Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes (Q2018540): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jda.2014.08.004
+Normal rank
@@ Property / OpenAlex ID @@
+W1973765739
@@ Property / OpenAlex ID: W1973765739 / rank @@
+Normal rank
@@ Property / cites work @@
+Some APX-completeness results for cubic graphs
@@ Property / cites work: Some APX-completeness results for cubic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Minimal identifying codes in trees and planar graphs with large girth
+Normal rank
@@ Property / cites work @@
+Complexity results for identifying codes in planar graphs
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Dominating sets for split and bipartite graphs
@@ Property / cites work: Dominating sets for split and bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On separating systems
@@ Property / cites work: On separating systems / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating Sets in Chordal Graphs
@@ Property / cites work: Dominating Sets in Chordal Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
+Normal rank
@@ Property / cites work @@
+Discriminating codes in (bipartite) planar graphs
@@ Property / cites work: Discriminating codes in (bipartite) planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
+Normal rank
@@ Property / cites work @@
+Approximation hardness of edge dominating set problems
+Normal rank
@@ Property / cites work @@
+Approximation hardness of dominating set problems in bounded degree graphs
+Normal rank
@@ Property / cites work @@
+Unit disk graphs
@@ Property / cites work: Unit disk graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3789614
@@ Property / cites work: Q3789614 / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating sets in perfect graphs
@@ Property / cites work: Dominating sets in perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+Monadic second-order evaluations on tree-decomposable graphs
+Normal rank
@@ Property / cites work @@
+Structure in Approximation Classes
@@ Property / cites work: Structure in Approximation Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Domination in convex and chordal bipartite graphs
@@ Property / cites work: Domination in convex and chordal bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the test cover problem
+Normal rank
@@ Property / cites work @@
+Domination, independent domination, and duality in strongly chordal graphs
+Normal rank
@@ Property / cites work @@
+Domination in permutation graphs
@@ Property / cites work: Domination in permutation graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of the Identifying Code Problem in Restricted Graph Classes
+Normal rank
@@ Property / cites work @@
+Identifying Codes in Line Graphs
@@ Property / cites work: Identifying Codes in Line Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The Rectilinear Steiner Tree Problem is $NP$-Complete
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2867320
@@ Property / cites work: Q2867320 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4368728
@@ Property / cites work: Q4368728 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4368729
@@ Property / cites work: Q4368729 / rank @@
+Normal rank
@@ Property / cites work @@
+NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+On a new class of codes for identifying vertices in graphs
+Normal rank
@@ Property / cites work @@
+How complex are random graphs in first order logic?
+Normal rank
@@ Property / cites work @@
+Domination and total domination on asteroidal triple-free graphs
+Normal rank
@@ Property / cites work @@
+Identifying Codes and Covering Problems
@@ Property / cites work: Identifying Codes and Covering Problems / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
+Normal rank
@@ Property / cites work @@
+Identifying and Locating–Dominating Codes in (Random) Geometric Networks
+Normal rank
@@ Property / cites work @@
+Approximation and Online Algorithms
@@ Property / cites work: Approximation and Online Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3279628
@@ Property / cites work: Q3279628 / rank @@
+Normal rank
@@ Property / cites work @@
+Domination and location in acyclic graphs
@@ Property / cites work: Domination and location in acyclic graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3684148
@@ Property / cites work: Q3684148 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximability of identifying codes and locating-dominating codes
+Normal rank
@@ Property / cites work @@
+Edge Dominating Sets in Graphs
@@ Property / cites work: Edge Dominating Sets in Graphs / rank @@
+Normal rank