%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "bergerbbl95.ltx",
%%%     date      = "20 November 1995",
%%%     time      = "21:41:33 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "26146 107 469 3878",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 1995 by ACM, Inc.
%%%                  Permission to make digital or hard copies of part
%%%                  or all of this work for personal or classroom use
%%%                  is granted without fee provided that copies are
%%%                  not made or distributed for profit or direct
%%%                  commercial advantage and that copies bear this
%%%                  notice and the full citation on the first page.
%%%                  Copyrights for components of this work owned by
%%%                  others than ACM must be honored. Abstracting with
%%%                  credit is permitted. To copy otherwise, to
%%%                  republish, to post on servers, or to redistribute
%%%                  to lists, requires prior specific permission
%%%                  and/or a fee. Request permissions from
%%%                  Publications Dept, ACM Inc., fax +1 (212)
%%%                  869-0481, or permissions@acm.org.
%%%                  
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{BergerBBL95}

\title{Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing}

\author{Bonnie Berger \and Martin Brady \and Donna Brown \and Tom Leighton}

\Pages{500--542}

\Month{March}

\Year{1995}

\Volume{42}

\Number{2}

\maketitle

\begin{abstract}

This paper presents algorithms for routing channels with $L\ge2$ 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.

\end{abstract}

\begin{categories}

B.7.2[placement and routing]; F.2.2[routing and layout]

\end{categories}

\begin{terms}

Design, Theory

\end{terms}

\begin{keywords}

Channel routing, multilayer routing, VLSI layout

\end{keywords}

\end{document}
