The \(k\)-hop connected dominating set problem: hardness and polyhedra

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

zbMATH Keywords

polytopehardnessfacets\(k\)-hop connected dominating set

Mathematics Subject Classification ID

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