Compact floor-planning via orderly spanning trees
Resource
Journal of Algorithms 48 (2): 441-451
Journal
Journal of Algorithms
Journal Volume
48
Journal Issue
2
Pages
441-451
Date Issued
2003-09
Date
2003
Author(s)
Abstract
Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size (n - 1) × [(2n + 1)/3]. Lower bounds on the worst-case area for floor-planning any plane triangulation are also provided in the paper. © 2003 Elsevier Inc. All rights reserved.
SDGs
Other Subjects
Algorithms; Computational complexity; Theorem proving; VLSI circuits; Floor-planning; Trees (mathematics)
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
15.pdf
Size
176.12 KB
Format
Adobe PDF
Checksum
(MD5):7be339ab0b0f8b8e6b811f3c1427015f