We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Extended formulations for stable set polytopes of graphs without two disjoint odd cycles.
- Authors
Conforti, Michele; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
- Abstract
Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size- O (n 2) extended formulation for the stable set polytope of G.
- Subjects
POLYTOPES; POLYNOMIAL time algorithms; GRAPH connectivity; INTEGERS; ALGORITHMS
- Publication
Mathematical Programming, 2022, Vol 192, Issue 1/2, p547
- ISSN
0025-5610
- Publication type
Article
- DOI
10.1007/s10107-021-01635-0