A divide-and-conquer approach to the minimum k-way cut problem
This paper presents algorithms for computing a minimum 3-way cut and a minimum 4-way cut of an undirected weighted graph G. Let G = (V, E) bean undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k-way cut problem with fixed k, that requires O (n(4)) and O (n(6)) maximum flow computations, respectively, to compute a minimum 3-way cut and a minimum 4-way cut of G. In this paper we first show some properties on minimum 3-way cuts and minimum 4-way cuts, which indicate a recursive structure of the minimum k-way cut problem when k = 3 and 4. Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3-way cut and a minimum 4-way cut of G, which require O(n(3)) and O(n(4)) maximum flow computations, respectively.
minimum k-way cut undirected weighted graph maximum flow computation recursive structure deterministic algorithm