Loading Events

← Back to Events

November 2019

:

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number

November 12 Tuesday @ 4:30 PM - 5:30 PM
Room B232, IBS (기초과학연구원)

It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs.  The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles.  The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is …

Find out more »
+ Export Events