A decomposition approach for the minimum connected dominating set problem

DOI10.3969/J.ISSN.1673-5862.2017.04.008zbMATH Open1399.90202MaRDI QIDQ3175482FDOQ3175482

Defeng Sun, Bin Wang

Publication date: 18 July 2018

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

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)

Cited In (2)

• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut

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)