The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm

DOI10.1007/978-3-642-21527-8_21zbMath1345.90102OpenAlexW173023041MaRDI QIDQ3091498

No author found.

Publication date: 9 September 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21527-8_21

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (17)

The \(p\)-arborescence star problem: formulations and exact solution approaches ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ The tree-star problem: a formulation and a branch-and-cut algorithm ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Binary programming formulations for the upper domination problem ⋮ Complexity and lowers bounds for power edge set problem ⋮ A compact mixed integer linear formulation for safe set problems ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ The minimum weakly connected independent set problem: polyhedral results and branch-and-cut ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ Integer linear programming models for the weighted total domination problem ⋮ A branch-and-Benders-cut approach for the fault tolerant regenerator location problem ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ On connected dominating sets of restricted diameter

This page was built for publication: The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm