Abstract
The problems studied here belong to a class called graph partition. They are combinatorial problems which consist of finding a partition of vertices into components in order to optimise a given measure. A variety of applications have been suggested, such as communication cost minimisation in parallel computing systems, clustering problems, VLSI design, and network reliability. A 0-1 integer programming is proposed first to define and solve the k-cut problem. Then, an efficient branch-and-bound algorithm is developed to solve this problem. As evidence of the utility of the proposed approach, the extensive computational results on random test problems are presented. In computational experiments on problems with up to 37 vertices, the proposed branch-and-bound algorithm is more efficient when compared to two branch-and-bound algorithms that are the same but without some bounds and dominance rules, and the proposed 0-1 integer programming model. The results show that both the lower and upper bounds are very tight, and the branch-and-bound algorithm performs very well.