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

DOI10.1016/j.disopt.2016.04.006zbMath1387.90277OpenAlexW2406503936MaRDI QIDQ1751176

Djelloul Mameri, Jean Mailfert, Fatiha Bendali

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

polytopesvalid inequalitiesbranch-and-cutgraph operationsweakly connected independent set

Mathematics Subject Classification ID

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

Related Items (1)

The weakly connected independent set polytope in corona and join of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Domination, independent domination, and duality in strongly chordal graphs
• Projection, lifting and extended formulation integer and combinatorial optimization
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Clustering and domination in perfect graphs
• On weakly connected domination in graphs
• On the independent dominating set polytope
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS

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