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 subsets 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 that runs in O(nk−2(nF(n
m) + C2(n
m) + n2)) = O(mnk log(n2=m)) time, where F(n
m) and C2(n
m) denote respectively the time bounds required to solve the maximum flow prob- lem and the minimum 2-way cut problem in G. The bounds Õ(mn5) for k = 5 and Õ(mn6) for k = 6 improve the previous best randomized bounds Õ(n8) and Õ (n10), respectively.