Polyhedral results on the stable set problem in graphs containing even or odd pairs

DOI10.1007/s10107-017-1168-xzbMath1405.90081OpenAlexW2623907872WikidataQ114228502 ScholiaQ114228502MaRDI QIDQ1785209

Jonas T. Witt, Marco E. Lübbecke, Bruce A. Reed

Publication date: 28 September 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1168-x

zbMATH Keywords

integer programmingstable set polytopestable set problemeven pairsodd pairs

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (1)

The strength of Dantzig-Wolfe reformulations for the stable set and related problems

Cites Work

• Unnamed Item
• The strong perfect graph theorem
• Even pairs in Berge graphs
• A new conjecture about minimal imperfect graphs
• A new property of critical imperfect graphs and some consequences
• On certain polytopes associated with graphs
• Normal hypergraphs and the perfect graph conjecture. (Reprint)
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: Polyhedral results on the stable set problem in graphs containing even or odd pairs