An improved two-way partitioning algorithm with stable performance (VLSI)
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 10 (12) , 1502-1511
- https://doi.org/10.1109/43.103500
Abstract
A two-way partitioning algorithm is presented that significantly improves on the highly unstable results typically obtained from the traditional Kernighan-Lin-based algorithms. The algorithm groups highly connected components into clusters and rearranges the clusters into two final subsets with specified sizes. It is known that the grouping operations reduce the complexity, and thus improve the results, of partitioning very large circuits. However, if the grouping is inappropriate, the partitioning results may degenerate. To prevent degeneration, a ratio cut approach is used to do the grouping. By a series of experiments based on the tradeoff between cut weight and CPU time, the value which controls the resultant number of groups is determined. Good experimental results have been observed for cut weight and CPU timeKeywords
This publication has 11 references indexed in Scilit:
- An improved objective function for mincut circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- An evolution-based approach to partitioning ASIC systemsPublished by Association for Computing Machinery (ACM) ,1989
- Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithmsPublished by Association for Computing Machinery (ACM) ,1989
- Multiple-way network partitioningIEEE Transactions on Computers, 1989
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A proper model for the partitioning of electrical circuitsPublished by Association for Computing Machinery (ACM) ,1972
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970