Header menu link for other important links
X
New lower bound for channel routing
, Sudebkumar Pal P., Ajit Pal
Published in Publ by IEEE, Piscataway, NJ, United States
1993
Pages: 507 - 510
Abstract
Channel routing is a key problem in the physical design of VLSI chips. It is known that max(dmax, vmax) is a lower bound on the number of tracks required in the reserved two-layer Manhattan routing model, where dmax is the channel density and vmax is the length of the longest path in the vertical constraint graph. In this paper we propose a polynomial time algorithm that computes a better lower bound on the number of tracks required for routing. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer HVH routing model.