AN EFFICIENT AND PAST ALGORITHM FOR ROUTING OVER THE CELLS

A linear time algorithm for routing over the cells is presented. The a lgorithm tries to reduce maximum channel density by routing some conne ctions over the cells. The algorithm first defines a new scheme for ch annel representation and formulates the problem based on an intersecti on 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 kn own 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 previou s algorithms lake about 29.25 seconds on an average but our new algori thm needs only 5.6 seconds.