Abstract
In this dissertation, we study the cut enumeration problem and the minimum k-cut problem. For the cut enumeration problem, an efficient algorithm with Õ(n^2m) delay between two successive outputs has been known since 1992, due to Vazirani and Yannakakis, where Õ(f) denotes O(flog^c f) for some constant c. In this dissertation, an improved algorithm is presented. The delay of the presented algorithm is Õ(nm). Vazirani and Yannakakis's algorithm has been used as a basic subroutine in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For the minimum k-cut problem, two new divide-and-conquer approaches are presented. Let T(k) denote the time complexity of finding a minimum k-cut. The first one reduces an instance of the minimum k-cut problem to O(2^(k-1)kn^3) instances of the minimum (k-1)-cut problem. Thus, our first approach shows that T(k) = O(2^(k-1)kn^3T(k-1)). For k = 7, 8, 9, 10, this approach improves the previous upper bound by a factor of O(n^(11-k)). With some modifications, the approach can also find all minimum k-cuts in O(n^(3k-6)mlog (n^2/m)) time for any constant k >= 3. When k = 3, this result improves the previous upper bound for finding all minimum 3-cuts from Õ(n^4m) to Õ(n^3m). Our second approach reduces an instance of the minimum k-cut problem to O(n^(2*floor(k/2))m) instances of the minimum (ceiling(k/2))-cut problem. Thus, our second approach shows that T(k) = Õ(n^(2*floor(k/2))mT(ceiling(k/2))). For 10 <= k <= 28, this approach is more efficient than the previous upper bound. For example, for k = 10, 11, and 12, we improve the upper bound by a factor of O(n^4/m), O(n^5/m), and O(n^5/m), respectively.