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

DOI10.1016/J.ENDM.2015.07.011MaRDI QIDQ324721zbMATH OpenOpenAlexFDO

Authors 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

polytopefacetshardness\(k\)-hop connected dominating set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Connectivity (05C40)

Recommendations

• The k-hop connected dominating set problem: approximation and hardness
• An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Algorithm and hardness results on hop domination in graphs
• On the complexity of \(k\)-step and \(k\)-hop dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Algorithmic construction of sets for k -restrictions
• Approximation hardness of dominating set problems in bounded degree graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Enumeration of minimal dominating sets and variants
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Max-leaves spanning tree is APX-hard for cubic graphs
• Solving the connected dominating set problem and power dominating set problem by integer programming
• Steiner trees, connected domination and strongly chordal graphs
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• Vertex and edge covers with clustering properties: Complexity and algorithms

Cited in

(7)

• scientific article; zbMATH DE number 7278055 (Why is no real title available?)
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• The parameterized complexity of terminal monitoring set
• An integer programming approach for fault-tolerant connected dominating sets
• The \(k\)-hop connected dominating set problem: approximation and hardness
• An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center

This page was built for publication: The \(k\)-hop connected dominating set problem: hardness and polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324721)