Solving the replacement paths problem for planar directed graphs in O(n logn) time

TY - GEN

T1 - Solving the replacement paths problem for planar directed graphs in O(n logn) time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 21

PY - 2010

Y1 - 2010

N2 - 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).

AB - 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).

U2 - 10.1137/1.9781611973075.62

DO - 10.1137/1.9781611973075.62

M3 - Article in proceedings

SN - 978-0-89871-701-3

SP - 756

EP - 765

BT - Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Charikar, Moses

PB - Society for Industrial and Applied Mathematics

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -