The \(k\)-hop connected dominating set problem: approximation and hardness (Q1679503): Difference between revisions

@@ Property / cites work @@
+Minimal separators in \(P_4\)-sparse graphs
@@ Property / cites work: Minimal separators in \(P_4\)-sparse graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Connected domination and Steiner set on weighted permutation graphs
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4944976
@@ Property / cites work: Q4944976 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5692521
@@ Property / cites work: Q5692521 / rank @@
+Normal rank
@@ Property / cites work @@
+Max-leaves spanning tree is APX-hard for cubic graphs
+Normal rank
@@ Property / cites work @@
+A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
+Normal rank
@@ Property / cites work @@
+Optimal dynamic program for r-domination problems over tree decompositions
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
+Normal rank
@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+A linear time algorithm to list the minimal separators of chordal graphs
+Normal rank
@@ Property / cites work @@
+A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
+Normal rank
@@ Property / cites work @@
+Algorithms – ESA 2004
@@ Property / cites work: Algorithms – ESA 2004 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation hardness of dominating set problems in bounded degree graphs
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+The \(k\)-hop connected dominating set problem: hardness and polyhedra
+Normal rank
@@ Property / cites work @@
+Approximating connectivity domination in weighted bounded-genus graphs
+Normal rank
@@ Property / cites work @@
+Permutation graphs: Connected domination and Steiner trees
+Normal rank
@@ Property / cites work @@
+Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
+Normal rank
@@ Property / cites work @@
+Q2921717
@@ Property / cites work: Q2921717 / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Connected dominating set. Theory and applications
@@ Property / cites work: Connected dominating set. Theory and applications / rank @@
+Normal rank
@@ Property / cites work @@
+Q3579442
@@ Property / cites work: Q3579442 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
+Normal rank
@@ Property / cites work @@
+Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
+Normal rank
@@ Property / cites work @@
+Vertex and edge covers with clustering properties: Complexity and algorithms
+Normal rank
@@ Property / cites work @@
+A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
+Normal rank
@@ Property / cites work @@
+Algorithmic graph theory and perfect graphs
@@ Property / cites work: Algorithmic graph theory and perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for connected dominating sets
+Normal rank
@@ Property / cites work @@
+Improved methods for approximating node weighted Steiner trees and connected dominating sets.
+Normal rank
@@ Property / cites work @@
+Generalized split graphs and Ramsey numbers
@@ Property / cites work: Generalized split graphs and Ramsey numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation and intractability results for the maximum cut problem and its variants
+Normal rank
@@ Property / cites work @@
+Q4368728
@@ Property / cites work: Q4368728 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5503435
@@ Property / cites work: Q5503435 / rank @@
+Normal rank
@@ Property / cites work @@
+Weighted connected domination and Steiner trees in distance-hereditary graphs
+Normal rank
@@ Property / cites work @@
+Enumeration of Minimal Dominating Sets and Variants
+Normal rank
@@ Property / cites work @@
+Q4636441
@@ Property / cites work: Q4636441 / rank @@
+Normal rank
@@ Property / cites work @@
+Listing all Minimal Separators of a Graph
@@ Property / cites work: Listing all Minimal Separators of a Graph / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of r-dominating set on Graphs of Diameter (r + 1)
+Normal rank
@@ Property / cites work @@
+Doubly chordal graphs, steiner trees, and connected domination
+Normal rank
@@ Property / cites work @@
+The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
+Normal rank
@@ Property / cites work @@
+Approximation and Online Algorithms
@@ Property / cites work: Approximation and Online Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+A unified approach to domination problems on interval graphs
+Normal rank
@@ Property / cites work @@
+A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
+Normal rank
@@ Property / cites work @@
+A greedy approximation for minimum connected dominating sets
+Normal rank
@@ Property / cites work @@
+Steiner trees, connected domination and strongly chordal graphs
+Normal rank
@@ Property / cites work @@
+A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
+Normal rank