Share Email Print

Proceedings Paper

Improved Min-cut algorithm for multiple-way VLSI network partitioning
Author(s): Xiangdong Tan; Jiarong Tong; Pushan Tang
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

This paper presents an improved algorithm with a new cost function for multiple way network partitioning. The new cost function based on the net cut model proposed incorporate a penalty function to take account of the potential effects of cell's move. Experiments show that not only the result of the new cost function outperforms that of F-M's algorithm, but also the erratic defect of F-M's algorithm has been partially alleviated. This new algorithm is flexible enough to be applicable to different objective functions. The time complexity of the new algorithm is O(bN), where b is the number of blocks and N the number of nets.

Paper Details

Date Published: 22 March 1996
PDF: 6 pages
Proc. SPIE 2644, Fourth International Conference on Computer-Aided Design and Computer Graphics, (22 March 1996); doi: 10.1117/12.235559
Show Author Affiliations
Xiangdong Tan, Fudan Univ. (China)
Jiarong Tong, Fudan Univ. (China)
Pushan Tang, Fudan Univ. (China)

Published in SPIE Proceedings Vol. 2644:
Fourth International Conference on Computer-Aided Design and Computer Graphics
Shuzi Yang; Ji Zhou; Cheng-Gang Li, Editor(s)

© SPIE. Terms of Use
Back to Top