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.

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

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)