Abstract
Channel routing plays a central role in the physical design of VLSI chips. For two-layer dogleg-free channel routing, dm,, and v,,, are the two traditional lower bounds. In this paper, we present two efficient algorithms for computing a tighter lower bound for the channel routing problem. Our algorithms succe:j~fullyc ompute a lower bound of 26 for Deutsch's Difficult Example (DDE). The experiment on some large-scale randomly generated channel routing problems sholws that our lower bound algorithms are much tighter than the traditional lower bounds, and are much more efficient than Pals' algorithm [20] while obtaining similar (sometimes better) results.
Keywords
CAD on VLSI, physical design, channel routing, lower bound, DAG, transitive closure
Date of this Version
January 1995