TY - JOUR
T1 - A framework for solving VLSI graph layout problems
AU - Bhatt, Sandeep N.
AU - Thomson Leighton, Frank
PY - 1984/4
Y1 - 1984/4
N2 - A new divide-and-conquer framework for VLSI graph layout is introduced. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processors using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop a provably good layout strategy.
AB - A new divide-and-conquer framework for VLSI graph layout is introduced. Universally close upper and lower bounds are obtained for important cost functions such as layout area and propagation delay. The framework is also effectively used to design regular and configurable layouts, to assemble large networks of processors using restructurable chips, and to configure networks around faulty processors. It is also shown how good graph partitioning heuristics may be used to develop a provably good layout strategy.
UR - http://www.scopus.com/inward/record.url?scp=0021412333&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0021412333&partnerID=8YFLogxK
U2 - 10.1016/0022-0000(84)90071-0
DO - 10.1016/0022-0000(84)90071-0
M3 - Article
AN - SCOPUS:0021412333
SN - 0022-0000
VL - 28
SP - 300
EP - 343
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -