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  while obtaining similar (sometimes better) results.
CAD on VLSI, physical design, channel routing, lower bound, DAG, transitive closure
Date of this Version