An Improved Min-Cut Algonthm for Partitioning VLSI Networks
- 1 May 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (5) , 438-446
- https://doi.org/10.1109/tc.1984.1676460
Abstract
Recently, a fast (linear) heuristic for improving min-cut partitions of VLSI networks was suggested by Fiduccia and Mattheyses [6]. In this-paper we generalize their ideas and suggest a class of increasingly sophisticated heuristics. We then show, by exploiting the data structures originally suggested by them, that the computational complexity of any specific heuristic in the suggested class remains linear in the size of the network.Keywords
This publication has 4 references indexed in Scilit:
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Placement Capability Based on PartitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- 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