The k-hop connected dominating set problem: approximation and hardness
From MaRDI portal
(Redirected from Publication:1679503)
The \(k\)-hop connected dominating set problem: approximation and hardness
The \(k\)-hop connected dominating set problem: approximation and hardness
Recommendations
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- Algorithm and hardness results on hop domination in graphs
- TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
- An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
- Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
Cites work
- scientific article; zbMATH DE number 5764849 (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 1420907 (Why is no real title available?)
- scientific article; zbMATH DE number 2209525 (Why is no real title available?)
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- A Greedy Heuristic for the Set-Covering Problem
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- A greedy approximation for minimum connected dominating sets
- A linear time algorithm to list the minimal separators of chordal graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- A unified approach to domination problems on interval graphs
- Algorithmic graph theory and perfect graphs
- Algorithms – ESA 2004
- Approximating connectivity domination in weighted bounded-genus graphs
- Approximation algorithms for connected dominating sets
- Approximation and Online Algorithms
- Approximation and intractability results for the maximum cut problem and its variants
- Approximation hardness of dominating set problems in bounded degree graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Connected dominating set. Theory and applications
- Connected domination and Steiner set on weighted permutation graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Doubly chordal graphs, steiner trees, and connected domination
- Enumeration of minimal dominating sets and variants
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Generalized split graphs and Ramsey numbers
- Graph Classes: A Survey
- Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Linear-time certifying recognition algorithms and forbidden induced subgraphs
- Listing all Minimal Separators of a Graph
- Max-leaves spanning tree is APX-hard for cubic graphs
- Minimal separators in \(P_4\)-sparse graphs
- On the hardness of approximating minimum vertex cover
- Optimal dynamic program for \(r\)-domination problems over tree decompositions
- Permutation graphs: Connected domination and Steiner trees
- Revisiting connected dominating sets: an optimal local algorithm?
- Steiner trees, connected domination and strongly chordal graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Weighted connected domination and Steiner trees in distance-hereditary graphs
Cited in
(6)- TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
- Approximating \(k\)-connected \(m\)-dominating sets
- Algorithm and hardness results on hop domination in graphs
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- Approximating \(k\)-generalized connectivity via collapsing HSTs
- An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
This page was built for publication: The \(k\)-hop connected dominating set problem: approximation and hardness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679503)
