Header menu link for other important links
X
An algorithm for finding a non-trivial lower bound for channel routing
, S P PAL, A PAL
Published in Elsevier
1998
Volume: 25
   
Issue: 1
Pages: 71 - 84
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 deterministic polynomial time algorithm that computes a better and non-trivial lower bound on the number of tracks required for routing a channel without doglegging. This algorithm is also applicable for computing a lower bound on the number of tracks in the three-layer no-dogleg HVH routing as well as two- and three-layer restricted dogleg routing models. © 1998 Elsevier Science B.V. All rights reserved.
About the journal
JournalData powered by TypesetIntegration, the VLSI Journal
PublisherData powered by TypesetElsevier
ISSN0167-9260
Open AccessNo