31 citations · 56 across the 21 of their papers we have counts for
4 papers · 1 filter
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Michele Conforti, Samuel Fiorini, Tony Huynh +1
Let be an -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 maxi…
Minimum-cost integer circulations in given homology classes
Sarah Morell, Ina Seidel, Stefan Weltge
Let be a directed graph cellularly embedded in a surface together with non-negative cost on its arcs. Given any integer circulation in , we study the problem of finding a mi…
Persistency of Linear Programming Relaxations for the Stable Set Problem
Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter +1
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: f…
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh +2
Consider the family of graphs without node-disjoint odd cycles, where is a constant. Determining the complexity of the stable set problem for such graphs is a lon…