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

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