Title :
Approximation algorithms for VLSI partition problems
Author :
Leighton, Tom ; Makedon, Fillia ; Tragoudas, Spyros
Author_Institution :
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
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;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112608
