A Parameterized Approximation Scheme for Min $k$-Cut

Autor: Saket Saurabh, Vaishali Surianarayanan, Daniel Lokshtanov

Publikováno v: FOCS
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
61st IEEE Annual Symposium on Foundations of Computer Science, FOCS

In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8d7d2f5b42cafc607b70074c68a9f57d
https://doi.org/10.1137/20m1383197