Brunel University Research Archive (BURA) >
Research Areas >
Information Systems and Computing >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/1677

Title: Finding next-to-shortest paths in a graph
Authors: Krasikov, I
Noble, S D
Keywords: Graph algorithms
Computational complexity
Shortest paths
Publication Date: 2004
Publisher: Elsevier
Citation: Information Processing Letters, 92 (3): 117-119, Nov 2004
Abstract: We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest $(u,v)$-path is a shortest $(u,v)$-path amongst $(u,v)$-paths with length strictly greater than the length of the shortest $(u,v)$-path. In constrast to the situation in directed graphs, where the problem has been shown to be NP-hard, providing edges of length zero are allowed, we prove the somewhat surprising result that there is a polynomial time algorithm for the undirected version of the problem.
URI: http://bura.brunel.ac.uk/handle/2438/1677
ISSN: 0020-0190
Appears in Collections:Mathematics
Information Systems and Computing

Files in This Item:

File Description SizeFormat
shortestpaths.pdf120.85 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan