## February 26, Winter Quarter 2010: Theory Seminar

### 1:00pm in 1423 Bren Hall

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

## Lowell Trott, UC Irvine

Presenting a paper by Christian Wulff-Nilsen

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