An improved lower bound for channel routing problems

Historically, the only known lower bounds for the NP-complete channel routing problem (CRP) were the channel density and the length of the longest path in the vertical constraint graph. The authors use the two-layer reserved layer model where horizontal wires are on one layer and vertical wires on another. The authors review some previously known lower bounds for the reserved layer model. The proposed bound is tighter than the previously known trivial lower bounds. They also give an effective branch and bound algorithm for finding this improved bound. The approach integrates both vertical and horizontal constraints together to investigate the difficulty of CRPs.>