Subject: Book on calculating two alternative shortest paths

From: Wushao Wen <[email-masked]>
Date: Sun, 21 Jan 2001 20:09:32 -0800 (PST)

Hi,
    I remember there is a book or paper on how to calculate two shortest
paths from a source to a destination in a mesh network. The author also
mention it in this mailing list. Can someone please tell me the book name
or the author name?
   Thank you  very much!

Wushao Wen

---

From: "Manohar Ellanti" <[email-masked]>
Date: Mon, 22 Jan 2001 08:35:30 -0800

Wushao Wen,

 original work on this problem is done by Sururballe that provides not only
2-shortest paths but also for k-shortest paths in a mesh network.

You can find , specifically for 2-shortest paths, details in here;
J.W. Suurballe, R.E.Tarjan, "A Quick Method for Finding Shortest Pairs of
Disjoint Paths", Networks, Vol. 14, 1984 pp 325-336.

A generalized version of this algorithm for k-shortest paths can be found
here though I find it difficult to understand
J.W.Suurballe, "Disjoint Paths in a Network", Networks, Vol. 4., 1974,
pp125-145.

Some other work is also done for k-shortest paths by Ramesh Bhandari (He has
published a book and provided reference in a previous mail on this list),
Eppstein (UC,Berkely), Prof Grover at University of Alberta (also TRLabs).
Marali K and T.V.Laksham work has references to the above work as well.

Hope this answers your questions.

Manohar

---

From: Ramesh Bhandari <[email-masked]>
Date: Mon, 22 Jan 2001 10:02:13 -0500

Wushao Wen,

I am the author of the book in question. The title is "Survivable Networks:
Algorithms for Diverse Routing", Kluwer Academic Publishers (1999). The book
contains detailed algorithsm on calculating disjoint pair of paths,  maximally
disjoint paths, if full diversiry does not exit, K (>2) disjoint paths,  and
also for calculating disjoint paths in real-life fiber networks involving SRLG's
(or simply span-sharing links). The algorithms are in a form simpler than those
of Suurballe, whose versions are not easy to follow especially for K (>2)
disjoint paths, which was also the experience of  Manohar Ellanti (see below).

The above book can be obtained easily from fatbrain.com or by simply calling the
publisher at (781) 871-6600.

If there are any questions, please let me know.

Ramesh Bhandari

---

From: Tony Przygienda <[email-masked]>
Date: Mon, 22 Jan 2001 09:15:29 -0800

> publisher at (781) 871-6600.

Ramesh, read it a while ago and yes,  good book & a nifty, fairly easy to understand
algorithm ;-)

about the right length for a coast-to-coast plane reading

    -- tony