@InProceedings{KLRTx83,
  author = 	 { R. M. Karp and F. T. Leighton and R. L. Rivest and C. D. Thompson and U. Vazirani
                   and V. Vazirani },
  title = 	 { Global wire routing in two-dimensional arrays },
  pages = 	 { 453--459 },
  doi =          { 10.1109/SFCS.1983.23 },                  
  booktitle =    { Proceedings Twenth-Fourth Annual Symposium on Foundations of Computer Science },
  publisher =    { IEEE },
  editor = 	 { Lawrence Snyder },
  date =         { 1983 },                  
  issn =         { 0272-5428 },                  
  OPTyear =      { 1983 },                  
  OPTmonth = 	 { November 7--9, },
  eventdate =    { 1983-11-07/1983-11-09 },                  
  eventtitle =   { FOCS '83 },                  
  venue =        { Tucson, Arizona },                  
  abstract =     { 
                  We examine the problem of routing wires on a VLSI
                  chip, where the pins to be connected are arranged in
                  a regular rectangular array. We obtain tight bounds
                  for the worst-case ``channel-width'' needed to route
                  an $n \times n$ array, and develop provably good heuristics
                  for the general case. An interesting ``rounding
                  algorithm'' for obtaining integral approximations to
                  solutions of linear equations is used to show the
                  near-optimality of single-turn routings in the
                  worst-case.  
                 },
}