Fast randomized algorithms for computing minimum {3,4,5,6}-way cuts
Matthew S. Levine · 2000
A minimum k-way cut of an n-vertex, m-edge, weighted, undirected graph is a partition of the vertices into k sets that minimizes the total weight of edges with endpoints in dierent sets. We give new randomized algorithms to nd minimum 3-way and 4-way cuts, which lead to time bounds of O(mn k 2 log 3 n) time for k 6. This improves on the best previous time bounds by a factor of ~ n 2 ). 1 Introduction A minimum k-way cut of an n-vertex, m-edge, weighted, undirected graph is a partition of the vertices into k sets that minimizes the total weight of edges with endpoints in dierent sets. Asking for a minimum k-way cut is equivalent to asking for the edge set of minimum total weight whose removal would break the graph into at least k connected components. Our main motivations for studying minimum k-way cuts are that they are a natural property of graphs, and that they have received considerable attention in the past. Nagamochi and Ibaraki [11] also point to a number of appl...