https://scholars.lib.ntu.edu.tw/handle/123456789/155102
標題: | Compact floor-planning via orderly spanning trees | 作者: | Liao, Chien-Chih Lu, Hsueh-I Yen, Hsu-Chun |
公開日期: | 九月-2003 | 卷: | 48 | 期: | 2 | 起(迄)頁: | 441-451 | 來源出版物: | Journal of Algorithms | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0041928206&doi=10.1016%2fS0196-6774%2803%2900057-9&partnerID=40&md5=23329c18aaf87c8e5831564b8c0d3908 http://ntur.lib.ntu.edu.tw/bitstream/246246/142317/1/15.pdf |
DOI: | 10.1016/S0196-6774(03)00057-9 | SDG/關鍵字: | Algorithms; Computational complexity; Theorem proving; VLSI circuits; Floor-planning; Trees (mathematics) |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。