A faster algorithm for computing minimum 5-way and 6-way cuts in graphs

For an edge-weighted graph G with n vertices and m edges, the minimum k-way cut problem is to find a partition of the vertex set into k non-empty subs ets so that the weight sum of edges between different subsets is minimized. For this problem with k = 5 and 6, we present a deterministic algorithm th at runs in O(n(k-1)F(n, m)) = O(mn(k) log (n(2)/m)) time, where F(n, m) den otes the time bound required to solve the maximum flow problem in G. The bo unds (O) over tilde(mn(5)) for k = 5 and (O) over tilde(mn(6)) for k = 6 im prove the previous best randomized bounds (O) over tilde(n(8)) and (O) over tilde(n(10)), respectively.