A Polynomial Algorithm for the k-cut Problem for Fixed k
- 1 February 1994
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 19 (1) , 24-37
- https://doi.org/10.1287/moor.19.1.24
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 O(nk²/2−3k/2+4T(n, m)) 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.Keywords
This publication has 0 references indexed in Scilit: