%0 Journal Article %1 goldschmidt94 %A Goldschmidt, Olivier %A Hochbaum, Dorit S. %D 1994 %I INFORMS %J Mathematics of Operations Research %K min-cut %N 1 %P pp. 24-37 %T A Polynomial Algorithm for the k-Cut Problem for Fixed k %U http://www.jstor.org/stable/3690374 %V 19 %X The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in <tex-math>$O(n^k^2/2-3k/2+4T(n,m))$</tex-math> steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.

@article{goldschmidt94, abstract = {The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in <tex-math>$O(n^{k^{2}/2-3k/2+4}T(n,m))$</tex-math> steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.}, added-at = {2013-11-03T19:17:34.000+0100}, author = {Goldschmidt, Olivier and Hochbaum, Dorit S.}, biburl = {https://www.bibsonomy.org/bibtex/2d32a29eb98435f4495c403092e5db02d/ytyoun}, interhash = {d2082b6a1aea0a323f84afd68704239e}, intrahash = {d32a29eb98435f4495c403092e5db02d}, issn = {0364765X}, journal = {Mathematics of Operations Research}, keywords = {min-cut}, number = 1, pages = {pp. 24-37}, publisher = {INFORMS}, timestamp = {2013-11-03T19:17:34.000+0100}, title = {A Polynomial Algorithm for the k-Cut Problem for Fixed k}, url = {http://www.jstor.org/stable/3690374}, volume = 19, year = 1994 }