https://scholars.lib.ntu.edu.tw/handle/123456789/324070
標題: | On a new timing-driven routing tree problem | 作者: | Wong, D.F. Zhu, Kai Wong, C.K. YAO-WEN CHANG |
公開日期: | 1996 | 卷: | 4 | 起(迄)頁: | 420-423 | 來源出版物: | Proceedings - IEEE International Symposium on Circuits and Systems | 摘要: | In this paper, we consider a new model of timing-driven routing, based on the idea of finding minimum spanning trees (minimum routing cost) with bounded delays, in a multiple weighted graph. This problem is originally motivated by the timing-driven routing for FPGA's, and is applicable to other related problems in which multiple independent optimization objectives need to be considered simultaneously. We prove that this problem in general is NP-complete, and there exists no approximation algorithm with any constant bound for the problem if the triangle inequality does not hold. We give approximation algorithms with a guaranteed performance bound for the case where the routing cost satisfies the triangle inequality. Experimental results show that our algorithms are very promising. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-0029708494&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/324070 |
ISSN: | 02714310 | SDG/關鍵字: | Algorithms; Approximation theory; Computational complexity; Gates (transistor); Graph theory; Logic circuits; Mathematical models; Optimization; Switching functions; VLSI circuits; Approximation algorithm; Bounded delays; Field programmable gate arrays; Independent optimization objectives; Minimum routing cost; Minimum spanning trees; Timing driven routing tree problem; Circuit theory |
顯示於: | 電子工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。