Please use this identifier to cite or link to this item: http://rportal.lib.ntnu.edu.tw:80/handle/77345300/34323
Title: An efficient and fast algorithm for routing over the cells
Authors: 國立臺灣師範大學資訊教育研究所
張國恩
陳世旺
Chang, Kuo-En
Chen, Sei-Wang
Issue Date: 1-Jan-1996
Publisher: Hindawi Publishing Corporation
Abstract: A linear time algorithm for routing over the cells is presented. The algorithm tries to reduce maximum channel density by routing some connections over the cells. The algorithm first defines a new scheme for channel representation and formulates the problem based on an intersection graph derived from the new scheme. Then, a feasible independent set of the intersection graph is found for routing some subnets over the cells. The algorithm is implemented and evaluated with several well known benchmarks. In comparison with previous research, our results are satisfactory, and the algorithm takes substantially less CPU time than those of previous works. For Deutsch's difficult example, the previous algorithms take about 29.25 seconds on an average but our new algorithm needs only 5.6 seconds.
URI: http://rportal.lib.ntnu.edu.tw/handle/77345300/34323
ISSN: 1065-514X
Other Identifiers: ntnulib_tp_A0904_01_022
Appears in Collections:教師著作

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.