Please use this identifier to cite or link to this item:
|Title:||Finding next-to-shortest paths in a graph|
Noble, S D
|Keywords:||Graph algorithms;Computational complexity;Shortest paths|
|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.|
|Appears in Collections:||Mathematical Science|
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.