A Simple Branch-And-Bound Algorithm For The K-Cut Problem For Applications With K Target Vertices, E.G. Vlsi Design
- Publisher:
- Springer-Verlag London Ltd
- Publication Type:
- Journal Article
- Citation:
- International Journal Of Advanced Manufacturing Technology, 2002, 20 (1), pp. 63 - 71
- Issue Date:
- 2002-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2010004133OK.pdf | 128.25 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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 01 integer programming is proposed first to define and solve the k-cut problem. Then, an efficient branchand- 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 01 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.
Please use this identifier to cite or link to this item: