https://scholars.lib.ntu.edu.tw/handle/123456789/155364
標題: | Bubble Sort Approach to Channel Routing | 作者: | Chen, S.-S. Yang, C.-H. SAO-JIE CHEN |
公開日期: | 2000 | 卷: | 147 | 期: | 6 | 起(迄)頁: | 415-422 | 來源出版物: | IEE Proceedings-Computers and Digital Techniques | 摘要: | An efficient bubble-sort technique for solving the two-layer non-Manhattan channel routing problem is presented. The time and space complexities of our algorithm are O(kn) and O(n), respectively, where k is the number of sorting passes required and n is the total number of two-terminal nets in a routing channel. The algorithm is easily extended to handle the cases with multiterminal nets distributed in a channel. Various tests verify the efficiency of the bubble-sort based router. Experimental results indicate that the router is time-efficient for routing. A three-layer algorithm having O(kn) time based on an identical problem formulation is proposed for solving the non-Manhattan channel routing. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/144068 https://www.scopus.com/inward/record.uri?eid=2-s2.0-0034313230&doi=10.1049%2fip-cdt%3a20000810&partnerID=40&md5=05dc67ffedf3bf181b16813a4dc43f9a |
ISSN: | 13502387 | DOI: | 10.1049/ip-cdt:20000810 | SDG/關鍵字: | Algorithms; Communication channels (information theory); Computational complexity; Problem solving; Sorting; Bubble-sort technique; Channel routing; Routers |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。