DocumentCode
2663865
Title
Approximation algorithms for VLSI partition problems
Author
Leighton, Tom ; Makedon, Fillia ; Tragoudas, Spyros
Author_Institution
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fYear
1990
fDate
1-3 May 1990
Firstpage
2865
Abstract
Polynomial time approximation algorithms are described for several VLSI partitioning problems, including graph and hypergraph partitioning, and nonplanar edge deletion. The algorithms find solutions that are within a polylogarithmic factor of the optimal solution for several of the problems. All of the algorithms use the Leighton-Rao (7988) graph-separator algorithm as a subroutine
Keywords
VLSI; circuit layout; graph theory; integrated circuit technology; network topology; IC layout; Leighton-Rao algorithm subroutine; VLSI partition problems; graph-separator algorithm; hypergraph partitioning; nonplanar edge deletion; polynominal time approximation algorithms; Approximation algorithms; Circuit testing; Computer science; Laboratories; Mathematics; Particle separators; Partitioning algorithms; Polynomials; Very large scale integration; Virtual manufacturing;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location
New Orleans, LA
Type
conf
DOI
10.1109/ISCAS.1990.112608
Filename
112608
Link To Document