The MPLS WG Archive

["Sinha, Rakesh" <rsinha@ciena.com>]

A number of approximation algorithms (i.e. efficient algorithms with
guaranteed performance bound) for similar problems are described in Chapter
six of the book "Approximation algorithms for NP-hard problems", edited by
Dorit S. Hochbaum, PWS publishing company.
The book describes the problem in terms of k-connectivity which is
equivalent (by something called Menger's theorem) to having k disjoint
paths. 

regards,
---------------
Rakesh K. Sinha
Ciena Core Switching Division
10480 Ridgeview Court, Cupertino, CA 95014
Ph: (408) 366 4950, Fax: (408) 366 4867
email: rsinha@ciena.com 

> -----Original Message-----
> Manohar Ellanti wrote:
> 
> > 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
> >
> > ----- Original Message -----
> > From: "Wushao Wen" <wswen@ece.ucdavis.edu>
> > To: <mpls@UU.NET>
> > Sent: Sunday, January 21, 2001 8:09 PM
> > Subject: Book on calculating two alternative shortest paths
> >
> > > 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
> > >
>