A decomposition approach for the minimum connected dominating set problem

DOI10.3969/J.ISSN.1673-5862.2017.04.008MaRDI QIDQ3175482zbMATHFDO

Authors Bin Wang, Defeng Sun

Publication date 18 July 2018

zbMATH Keywords

integer programmingBenders decompositionminimum connected dominating setcombinatorial cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Communication networks in operations research (90B18)

Recommendations

• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Connected dominating set. Theory and applications
• Approximation algorithms for connected dominating sets
• A matheuristic approach for solving the 2-connected dominating set problem
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm

Cited in

(9)

• Connected dominating set. Theory and applications
• A decomposition approach for solving a broadcast domination network design problem
• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
• A matheuristic approach for solving the 2-connected dominating set problem
• Restricted swap-based neighborhood search for the minimum connected dominating set problem
• A game theoretic approach for minimal connected dominating set
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set

This page was built for publication: A decomposition approach for the minimum connected dominating set problem

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