A deterministic algorithm for finding all minimum k-way cuts
Let G = (V, E) be an edge-weighted undirected graph with n vertices and m edges. We present a deterministic algorithm to compute a minimum k-way cut of G for a given k. Our algorithm is a divide-and-conquer method based on a procedure that reduces an instance of the minimum k-way cut problem to O(n(2k-5)) instances of the minimum ([(k + root k)/2] + 1)-way cut problem, and can be implemented to run in O(n(4k)/((1- 1.71/root k)-31)) time. With a slight modi. cation, the algorithm can find all minimum k-way cuts in O(n(4k)/((1- 1.71/root k)-16)) time.
divide-and-conquer minimum cut multiway cut