The \(k\)-hop connected dominating set problem: approximation and hardness
From MaRDI portal
Publication:1679503
DOI10.1007/s10878-017-0128-yzbMath1384.90081OpenAlexW2600384081MaRDI QIDQ1679503
Phablo F. S. Moura, Yoshiko Wakabayashi, Rafael S. Coelho
Publication date: 9 November 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-017-0128-y
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The \(k\)-hop connected dominating set problem: hardness and polyhedra
- Max-leaves spanning tree is APX-hard for cubic graphs
- Connected dominating set. Theory and applications
- A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
- A greedy approximation for minimum connected dominating sets
- On the hardness of approximating minimum vertex cover
- A linear time algorithm to list the minimal separators of chordal graphs
- Minimal separators in \(P_4\)-sparse graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- A unified approach to domination problems on interval graphs
- Permutation graphs: Connected domination and Steiner trees
- Connected domination and Steiner set on weighted permutation graphs
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- Generalized split graphs and Ramsey numbers
- Approximation algorithms for connected dominating sets
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Algorithmic graph theory and perfect graphs
- A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Hardness of r-dominating set on Graphs of Diameter (r + 1)
- Enumeration of Minimal Dominating Sets and Variants
- Steiner trees, connected domination and strongly chordal graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- A Greedy Heuristic for the Set-Covering Problem
- Graph Classes: A Survey
- Listing all Minimal Separators of a Graph
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Optimal dynamic program for r-domination problems over tree decompositions
- Doubly chordal graphs, steiner trees, and connected domination
- A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Approximating connectivity domination in weighted bounded-genus graphs
- Approximation and intractability results for the maximum cut problem and its variants
- Algorithms – ESA 2004
- Approximation and Online Algorithms
This page was built for publication: The \(k\)-hop connected dominating set problem: approximation and hardness
