https://scholars.lib.ntu.edu.tw/handle/123456789/289914
標題: | Generalized terminal connectivity problem for multilayer layout scheme | 作者: | Tsai, C.-C. SAO-JIE CHEN Feng, W.-S. |
關鍵字: | electronic design automation; hyper-complete graph; minimal steiner tree; shortest connectivity path; terminal connectivity | 公開日期: | 1990 | 卷: | 22 | 期: | 7 | 起(迄)頁: | 423-433 | 來源出版物: | Computer-Aided Design | 摘要: | Given a set of n horizontal (or vertical) wire segments run on different layers with variable widths (or heights), and a set of m terminals placed on different layers and with arbitrary rectangular shapes, a generalization of the terminal connectivity problem (TCP) is considered. This TCP can be applied to facilitate the VLSI or PCB multi-layer layout. First, it is proved that this TCP is NP-hard by showing that it is equivalent to a minimal steiner tree problem, which has been proved NP-complete. Then an efficient algorithm for the TCP is presented which runs in O(m + (1 + c)nn) time (with some preprocessing work). Experimental results are given to verify the effectiveness of the algorithm. © 1990. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-0025493718&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/289914 |
ISSN: | 00104485 | DOI: | 10.1016/0010-4485(90)90107-N | SDG/關鍵字: | Computer Programming--Algorithms; Integrated Circuits--Layout; Printed Circuits; Electronic Design Automation; Hyper-Complete Graph; Minimal Steiner Tree; Multilayer Layout; Terminal Connectivity; Electronic Circuits |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。