The \(k\)-hop connected dominating set problem: hardness and polyhedra
From MaRDI portal
Publication:324721
DOI10.1016/j.endm.2015.07.011zbMath1347.05137OpenAlexW2219732409MaRDI QIDQ324721
Rafael S. Coelho, Phablo F. S. Moura, Yoshiko Wakabayashi
Publication date: 17 October 2016
Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.011
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)
Related Items
The \(k\)-hop connected dominating set problem: approximation and hardness, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Max-leaves spanning tree is APX-hard for cubic graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Algorithmic construction of sets for k -restrictions
- Enumeration of Minimal Dominating Sets and Variants
- The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
- Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
- Steiner trees, connected domination and strongly chordal graphs