# Solving the replacement paths problem for planar directed graphs in O(<em>n </em>log<em>n</em>) time

- Authors:
- Editor:
- Moses Charikar
- DOI:
- 10.1137/1.9781611973075.62
- Abstract:
- 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).
- ISBN:
- 9780898717013, 9781611973075
- Type:
- Conference paper
- Language:
- English
- Published in:
- Proceedings of the Twenty-first Annual Acm-siam Symposium on Discrete Algorithms, 2010, p. 756-765
- Main Research Area:
- Science/technology
- Publication Status:
- Published
- Review type:
- Peer Review
- Conference:
- 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
- Publisher:
- Society for Industrial and Applied Mathematics
- Submission year:
- 2010
- Scientific Level:
- Scientific
- ID:
- 2185943901