-
Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality
Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality
Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth …