Name
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 contrast 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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ipl.2004.06.020 | Inf. Process. Lett. |
Keywords | Field | DocType |
graph algorithms,undirected version,shortest paths.,surprising result,polynomial time algorithm,length zero,computational complexity,next-to-shortest path,preprint,directed graph,shortest path | Discrete mathematics,Graph,Combinatorics,Bound graph,Shortest path problem,Directed graph,Floyd–Warshall algorithm,Time complexity,Shortest-path tree,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
92 | 3 | 0020-0190 |
Citations | PageRank | References |
9 | 0.88 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| I. Krasikov | 1 | 127 | 23.65 |
| S. D. Noble | 2 | 83 | 9.56 |