Xref: utzoo comp.theory:568 comp.lsi:999 sci.math:10604
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!asuvax!mcdphx!dover!darla!waters
From: waters@darla.sps.mot.com (Strawberry Jammer)
Newsgroups: comp.theory,comp.lsi,sci.math
Subject: Re: Wanted: references on routing algorithms.
Message-ID: <2093@dover.sps.mot.com>
Date: 11 Apr 90 15:37:56 GMT
References: <137@centaure.UUCP> <905@gold.GVG.TEK.COM>
Sender: usenet@dover.sps.mot.com
Reply-To: waters@darla.sps.mot.com (Strawberry Jammer)
Organization: Hacker's haven
Lines: 36

In article <905@gold.GVG.TEK.COM> grege@gold.GVG.TEK.COM (Gregory Ebert) writes:
{In article <137@centaure.UUCP> cliff@centaure.UUCP (Cliff Dibble) writes:
{>I'm interested in algorithms for routing traces on printed circuit
{>boards. I'd greatly appreciate any references to the subject.
{>Thank you.
{>
{	I think you are looking for Lee's algorithm. It was published in the
{	Bell System Technical Journal, and applies to optimal routing of
{	cross-country phone calls. Talk about technology transfer !

Lee's algorithm was the first published (BSTJ Aug. 1956). Turns out that the
two problems have a lot in common. Lee's is still the basis for 90% of
all routers used today.

{	I believe the algorithm tries to establish a connection between 2
{	points by starting at each endpoint and working towards eachother.

Not quite, a better analogy is pouring water on a floor then watching the
wavefront cross as it spreads. Once the "target" get "wet" then you retrace
the "flow" to the source and you have a vaid route. Obviously all of that is
analogy, but it is quite close to what is simulated.

Lee's algorithm is gauranteed to find a rout if one exists, but has numerous
shortcomings. Look in the IEEE/ACM Design Automation Conference proceedings:
The 1989 Proceedings can be found under:
Library of Congress Cat no. 85-644924, ACM order no 477890, IEEE order no.
89H2734-2.

Every conference since it was founded (26 years!) has had a section on routing 
algorithms of one kind or another. Routing is a tough problem in the real
world.

           *Mike Waters    AA4MW/7  waters@dover.sps.mot.com *
 
You are in a twisting maze of little passages, all different.