A combinatorial column generation algorithm for the maximum stable set problem

DOI10.1016/S0167-6377(96)00038-7MaRDI QIDQ1374381zbMATH OpenFDO

Authors Jean-Marie Bourjolly, G. Laporte, Hélène Mercure

Publication date 4 December 1997

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-6377(96)00038-7

zbMATH Keywords

branch-and-boundcliquescolumn generationcutting plane algorithmlower boundsminimum cover of a graphodd cyclesstable set

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• An exact algorithm for the maximum stable set problem
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
• A Column Generation Approach for Graph Coloring

Cites work

• A branch and bound algorithm for the maximum clique problem
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• Finding a Maximum Clique in an Arbitrary Graph
• scientific article; zbMATH DE number 3845638 (Why is no real title available?)
• scientific article; zbMATH DE number 956842 (Why is no real title available?)
• scientific article; zbMATH DE number 956850 (Why is no real title available?)
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Node-weighted graphs having the König-Egerváry property
• Paths, Trees, and Flowers
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Vertex packings: Structural properties and algorithms

Cited in

(8)

• Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
• Solving hard set covering problems
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• Column-Generation in Integer Linear Programming
• Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
• Searching for optimal integer solutions to set partitioning problems using column generation
• Block linear majorants in quadratic 0--1 optimization
• The travelling preacher, projection, and a lower bound for the stability number of a graph

This page was built for publication: A combinatorial column generation algorithm for the maximum stable set problem

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