Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

TY - UNPB

T1 - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

AU - Wulff-Nilsen, Christian

PY - 2009

Y1 - 2009

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 linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).

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 linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).

M3 - Working paper

SP - 1

EP - 21

BT - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

PB - Datalogisk Institut

CY - København

ER -