DocumentCode :
1150619
Title :
An Improved Min-Cut Algonthm for Partitioning VLSI Networks
Author :
Krishnamurthy, Balakrishnan
Author_Institution :
General Electric Research and Development Center
Issue :
5
fYear :
1984
fDate :
5/1/1984 12:00:00 AM
Firstpage :
438
Lastpage :
446
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 :
Partitioning algorithms; VLSI layout; Computational complexity; Costs; Data structures; Design automation; Independent component analysis; Partitioning algorithms; Research and development; Terminology; Very large scale integration; Partitioning algorithms; VLSI layout;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.1984.1676460
Filename :
1676460
Link To Document :
بازگشت