@InProceedings{RF82,
  author = 	 { Ronald L. Rivest and Charles M. Fiduccia },
  title = 	 { A `Greedy' Channel Router },
  pages = 	 { 418--424 },
  booktitle =    { Proceedings 19th IEEE Design Automation Conference },
  OPTeditor = 	 {},
  date =         { 1982 },                  
  eventtitle =   { DAC '82 },                  
  OPTyear = 	 { 1982 },
  OPTmonth = 	 { June 14--16, },
  eventdate =    { 1982-06-14/1982-06-16 },                  
  venue =        { Las Vegas, Nevada },                  
  publisher =    { IEEE },
  OPTannote = 	 { Best paper award. },
  abstract =     {
         We present a new, ``greedy'' channel-router that is
         quick, simple, and highly effective.  It \emph{always
         succeeds}, usually using no more than one track more
         than required by channel density. (It may be forced
         in rare cases to make a few connections ``off the end''
         of the channel, in order to succeed.)  It assumes that all
         pins and wiring lie on a common grid, and that vertical
         wires are on one layer, horizontal on another. 
         \par
         The greedy router wires up the channel in a left-to-right
         column-by-column manner, wiring each column completely
         before starting on the next.  Within each column the
         router tries to maximize the utility of the wiring 
         produced, using simple, ``greedy'' heuristics.
         It may place a net on more than one track for a few
         columns, and ``collapse'' the net to a single
         track later on, using a vertical jog.  It may also
         use a jog to move a net to a track closer to its
         pin in some future column.  The router may occasionally
         add a new track to the channel, to avoid
         ``getting stuck''.                  
                 },
}