In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linearspace algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).
Proceedings of the Twenty-first Annual Acm-siam Symposium on Discrete Algorithms, 2010, p. 756-765
Main Research Area:
21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010