Abstract
The k-cut problem is a NP-hard generalization of the min-cut problem. It is to separate a weighted graph with k specified vertices into k components of unspecified size such that the total weight between components is minimized. In this paper, we develop an effective branch-and-bound algorithm to solve the k-cut problem.