Abstract
Let G = (V, E) be an undirected graph with vertex set V and edge set E. Let n = |V| and m = |E|. Each e Î E has a positive weight. For k ³ 2, the minimum k-way cut problem is to find a set of edges whose removal partitions V into k non-empty disjoint subsets such that the total weight of removed edges is minimum. The minimum k-way cut problem is practical and important. In 1994, it was proved that the minimum k-way cut problem is NP-Hard when k is a variable. In the same paper, an time algorithm was also provided for any constant k. The problem of finding the minimum 2-way cut has been extensively studied. The currently best time complexity for this problem is O(nm + n2log n). In 1997, Burlet and Goldschmidt proposed an O(n3m + n4log n) time algorithm for k = 3. In 1999, Nagamochi and Ibaraki proposed faster algorithms for k = 4, 5, and 6. In this thesis, we study the k-way cut problem for k = 3, 4, 5, and 6. First, we present an improved algorithm for k = 3. The algorithm requires O(nm2 + n2mlog n) time. Then, by using the improved algorithm as a key procedure, improved algorithms for k = 4, 5, and 6 are proposed, which require O(nk-2m2 + nk-1mlog n) time.