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\left( {n^{k - 2} \left( {nF\left( {n,m} \right) + C_2 \left( {n,m} \right) + n^2 } \right)} \right) = O\left( {mn^k \log \left( {n^2 /m} \right)} \right) $ O\left( {n^{k - 2} \left( {nF\left( {n,m} \right) + C_2 \left( {n,m} \right) + n^2 } \right)} \right) = O\left( {mn^k \log \left( {n^2 /m} \right)} \right) time, where F(n,m) and C ₂ (n,m) denote respectively the time bounds required to solve the maximum flow problem and the minimum 2-way cut problem in G. The bounds $ \tilde O\left( {mn^5 } \right) $ \tilde O\left( {mn^5 } \right) for k = 5 and $ \tilde O\left( {mn^6 } \right) $ \tilde O\left( {mn^6 } \right) for k = 6 improve the previous best randomized bounds $ \tilde O\left( {n^8 } \right) $ \tilde O\left( {n^8 } \right) and $ \tilde O\left( {n^{10} } \right) $ \tilde O\left( {n^{10} } \right) , respectively.