@Article{RF83,
  author = 	 { Ronald L. Rivest and Charles M. Fiduccia },
  title = 	 { A `greedy' channel router },
  journal = 	 { Computer-Aided Design },
  issn =         { 0010-4485 },
  OPTyear = 	 { 1983 },
  OPTmonth = 	 { May },
  date =         { 1983-05 },                  
  volume = 	 { 15 },
  number = 	 { 3 },
  doi =          { 10.1016/0010-4485(83)90079-9 },
  url =          { http://www.sciencedirect.com/science/article/pii/0010448583900799 },
  pages = 	 { 135--140 },
  publisher =    { Butterworth },                  
  keywords =     { integrated circuits, layout, routing }, 
  htmlnote =     { Reprinted in <a href="#RF88">RF88</a>. },
  abstract =     {
       A `greedy' channel router is presented.  It is quick, simple,
       and effective.  It always succeeds, usually using no more than
       one track more than required by the channel density.  It may be 
       forced in rate 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.  The greedy router wires the channel left-to-right, column-by-column,
       wiring each column completely before starting the next.  Within each column
       the router tries to maximize the utility of the wiriting 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 one, using a 
       vertical job.  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.
                    },
}