A Minimum-Impact Routing Algorithm

A routing heuristic is presented that routes two-terminal nets one at a time, for each net choosing the path so as to avoid adversely impacting the nets not yet routed. An algorithm is presented and proved to correctly implement this heuristic; the computational complexity of that algorithm is shown to be polynomially bounded, but perhaps still too great to be of practical use. Another, speedier algorithm is presented that seems to approximate the heuristic rather closely. Strong evidence is given that the Lee routing algorithm is in some sense inadequate to implement this heuristic. The heuristic has been applied, with very encouraging results, to a specific routing problem: the routing of a channel in which all four sides of the channel may contain terminals. This problem arises in the layout of custom VLSI.