A track-by-track routing algorithm based on a greedy heuristic on density structure is presented. By applying a dynamic programming technique using an accurate criterion of density structure, the algorithm guarantees finding a set of wire segments for a track whose routing can decrease the channel density by one, if it exists. It is believed that none of the existing track-by-track routers can achieve this even by resorting to exhaustive search. With its accurate calculation in selecting wire segments in each track, the new two-layer router solves Deutsch's difficult example in 19 tracks in the two-layer restricted-Manhattan model by a simple density-related function, and the extended three-, four-, and five-layer routers also outperform other routers without backtracking, rerouting, or routing transformation. The experimental results are presented for performance comparison.>

A general approach for the channel routing problem is presented as a framework for a class of heuristic routing algorithms. The algorithm is shown to possess a backtracking capability that increases the chance of completing the routing with a minimum number of tracks. Since the concepts described are general, they can be applied to other channel problems, such as switchbox routing, three-layer routing, and multilayer routing, or even to the overlap model, with only a few modifications. It is shown that track-oriented greedy algorithms can be modified to solve other channel routing problems. As examples, the algorithm is modified to solve the Manhattan switch-box problem and channel routing problems in the overlap and knock-knee models. Preliminary results show that the modified algorithms have good performance and show strong potential to outperform existing algorithms. Applying the algorithm MCRP-ROUT to the benchmark Deutsch's difficult problem and Burstein's difficult problem, routing solutions of 19 tracks and six tracks, respectively, were obtained.>