Search by article title, author,
keywords, and DOI

Call for papers for the special issue “Prevention and Treatment of Addictive Behaviors on Campus” (Final submission deadline: 2021/8/31)      The Journal of Research in Education Sciences will no longer provide printed copies      Call for papers for the special issue “Educational Research Related to Southeast Asian Countries” (Final submission deadline: 2018/12/31)     

Journal directory listing - Volume 31-41 (1986-1996) - Volume 38 (1993)
Back

Reducing Channel Density by Routing Over The Cells Author: Kuo-En Chang(Department of Information and Computer Education, National Taiwan Normal University)

Abstract：

A linear time algorithm for greater reduction of maximum channel den-sity by routing over the cells is presented. The algorithm first models the problem as a new scheme of zone representation and two intersected graphs for two sides of the channel. Then, a feasible independent set of each graph is found to represent the subnets that are efficient to be routed over the cells at the corresponding side of channel. The algorithm is implemented and evaluated by the tests of famous benchmarks. In comparison with previous re-search, our results are satisfactory while the algorithm takes less CPU time than those of previous works. For Deutsch's difficult example, the previous algorithm takes about 29.25 seconds while we need only 5.6 seconds.

《Full Text》