The MPLS-OPS Archive

[Irwin Lazar <ilazar@mplsrc.com>]

Forwarded:

From: "Awduche, Daniel" <awduche@movaz.com>
>To: "Ramesh Bhandari" <bhandari@hotair.hobl.lucent.com>,
>    "Chrysostomos Tziouvaras" <tziou@ics.forth.gr>
>Cc: <mpls-ops@mplsrc.com>, <mpls@UU.NET>, <IP-Optical@lists.bell-labs.com>,
>    "Awduche, Daniel" <awduche@movaz.com>
>X-MIME-Autoconverted: from quoted-printable to 8bit by 
>host.secure4-hosting.net id f7GFhR522007
>X-Diagnostic: Not on the accept list
>X-Envelope-To: mpls-ops
>
>The 'K-Shortest Path' problem is well known and
>well studied (dating back to the late 1950's).
>Many different versions of this problem exist,
>subject to various types of restrictions.
>
>There are solution techniques based on improvements
>to Dijkstra's algorithm, and many others based
>on network flows and dynamic programming methods.
>Some approaches involve elegant graph transformations
>(as was the case, for example, in Ramesh's book on
>diverse routing).
>
>In addition to the references mentioned by Ramesh,
>the works of David Eppstein (and the references
>therein) may be of interest:
><http://www.ics.uci.edu/~eppstein/pubs/all.html>.
>
>CAVEAT:-- Many theoretical versions of the K-Shortest
>Path problem do not require the paths to be simple
>(i.e. loop-free).
>
>Yes, the K-Shortest Path problem may have relevance in
>optical connection routing, especially when considering
>wavelength assignment, optical impairments, and other
>constraints.
>
>Cheers,
>/Dan
>
>
> > -----Original Message-----
> > From: Ramesh Bhandari [mailto:bhandari@hotair.hobl.lucent.com]
> > Sent: Tuesday, August 14, 2001 1:37 PM
> > To: Chrysostomos Tziouvaras
> > Cc: mpls-ops@mplsrc.com; mpls@UU.NET; IP-Optical@lists.bell-labs.com
> > Subject: [IP-Optical] Re: An algorithm for calculating all
> > paths between
> > an s-d pair
> >
> >
> > Hi Chrysostomos,
> >
> > I believe you are searching for the K-shortest path algorithm, which
> > provides paths for a given pair of nodes in ascending order of their
> > lengths. An example website for information on this is
> > http://www.mat.uc.pt/~eqvm/cientificos/investigacao/r_papers.html#mps.
> >
> > But, if you are looking for algorithms for K-disjoint paths, these can
> > be found in my book: "Survivable Networks: Algorithms for Diverse
> > Routing", Kluwer Academic Publishers (1999).
> >
> > Regards,
> >
> > Ramesh
> >
> > Chrysostomos Tziouvaras wrote:
> > >
> > > Hi,
> > > I am searching for an algorithm for calculating all paths
> > between an s-d
> > > pair. Can you provide me pointers to books or URLs?
> > >
> > > Thanks
> > > Chrysostomos
> >
> > _______________________________________________
> > IP-Optical mailing list
> > IP-Optical@lists.bell-labs.com
> > http://lists.bell-labs.com/mailman/listinfo/ip-optical
> >

-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml