A framework for solving VLSI graph layout problems

Sandeep N. Bhatt, Frank Thomson Leighton

Research output: Contribution to journalArticlepeer-review

328 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)300-343
Number of pages44
JournalJournal of Computer and System Sciences
Volume28
Issue number2
DOIs
StatePublished - Apr 1984

Fingerprint

Dive into the research topics of 'A framework for solving VLSI graph layout problems'. Together they form a unique fingerprint.

Cite this