Approximation algorithms for VLSI partition problems
- 4 December 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2865-2868 vol.4
- https://doi.org/10.1109/iscas.1990.112608
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
This publication has 10 references indexed in Scilit:
- The Test Engineer's Assistant: a support environment for hardware design for testabilityComputer, 1989
- A New Heuristic for Partitioning the Nodes of a GraphSIAM Journal on Discrete Mathematics, 1988
- 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
- Optimization by simulated annealing: Quantitative studiesJournal of Statistical Physics, 1984
- Finding small simple cycle separators for 2-connected planar graphs.Published by Association for Computing Machinery (ACM) ,1984
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970