A combinatorial column generation algorithm for the maximum stable set problem

DOI10.1016/S0167-6377(96)00038-7zbMath0892.90176MaRDI QIDQ1374381

Gilbert Laporte, Jean-Marie Bourjolly, Hélène Mercure

Publication date: 4 December 1997

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

zbMATH Keywords

column generationbranch-and-boundstable setlower boundsodd cyclescliquescutting plane algorithmminimum cover of a graph

Mathematics Subject Classification ID

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

Related Items (5)

Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ Solving hard set covering problems ⋮ Block linear majorants in quadratic 0--1 optimization ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Column-Generation in Integer Linear Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• 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
• Finding a Maximum Clique in an Arbitrary Graph
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Vertex packings: Structural properties and algorithms
• Paths, Trees, and Flowers
• A branch and bound algorithm for the maximum clique problem

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