The minimum weakly connected independent set problem: polyhedral results and branch-and-cut

DOI10.1016/J.DISOPT.2016.04.006MaRDI QIDQ1751176zbMATH OpenOpenAlexFDO

Authors F. Bendali, J. Mailfert, Djelloul Mameri

Publication date 24 May 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2016.04.006

zbMATH Keywords

branch-and-cutgraph operationspolytopesvalid inequalitiesweakly connected independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Connectedness of weak minimal solution set for set optimization problems
• On approximating the minimum independent dominating set
• On minimum cutsets in independent domination vertex critical graphs
• scientific article; zbMATH DE number 867663
• A decomposition approach for the minimum connected dominating set problem
• On the complexity of the minimum independent set partition problem

Cites work

• A survey of the algorithmic aspects of modular decomposition
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Clustering and domination in perfect graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• On the independent dominating set polytope
• On weakly connected domination in graphs
• Projection, lifting and extended formulation integer and combinatorial optimization
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm

Cited in

(2)

• The weakly connected independent set polytope in corona and join of graphs
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm

This page was built for publication: The minimum weakly connected independent set problem: polyhedral results and branch-and-cut

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