Journal of the ACM Bibliography

Bonnie Berger, Martin Brady, Donna Brown, and Tom Leighton. Nearly optimal algorithms and bounds for multilayer channel routing. Journal of the ACM, 42(2):500-542, March 1995. [BibTeX entry]

This paper presents algorithms for routing channels with L > 2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d + O(\sqrt{d}) tracks to route two-terminal net problems and 2d + O(\sqrt{d}) tracks to route multiterminal nets. We also show that d + \Omega(log d) tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generalize the algorithm to unrestricted multilayer routing and use only d/(L-1) + O(\sqrt{d/L}+1) tracks for two-terminal net problems (within O(\sqrt{d/L}+1) tracks of optimal) and d/(L-2) + O(\sqrt{d/L}+1) tracks for multiterminal net problems (within a factor of (L-1)/(L-2) times optimal). We demonstrate the generality of our routing strategy by showing that it can be used to duplicate some of the best previous upper bounds for other models (two-layer Manhattan routing and two- and three-layer knock-tree routing of two-terminal, two-sided nets), and gives a new upper bound for routing with 45-degree diagonal wires. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: B.7.2 [Integrated Circuits]: Design Aids -- placement and routing; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- routing and layout

General Terms: Design, Theory

Additional Key Words and Phrases: Channel routing, multilayer routing, VLSI layout

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database