Output details
11 - Computer Science and Informatics
University of Leeds
Combinatorial optimization with 2-joins
<13>First time 2-joins are used in optimization algorithms:
general techniques are developed and applied to well known problems.
Significant impact has been rapid: (i) Building on this work and joining forces with Chudnovsky, we obtained optimization algorithms for perfect graphs with no skew partition. (ii) This paper’s general proof of existence of extreme 2-joins in graphs with no star cutset was then used by Aboulker, Radovanović, Trotignon, Trunck and Vušković to prove a 20-year old conjecture about linear balanced matrices [Vušković4]. (iii) Vušković secured follow up EPSRC grant (EP/K016423/1) with Trotignon and Chudnovsky (winner of MacArthur Fellowship) as named collaborators.