Solving the Replacement Paths Problem for Planar Directed Graphs in O(<em>n</em>log<em>n</em>) Time - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Department of Computer Science, Faculty of Science, Københavns Universitet^{2} The APL Section, Department of Computer Science, Faculty of Science, Københavns Universitet^{3} Administration, Department of Computer Science, Faculty of Science, Københavns Universitet^{4} Administration, Department of Computer Science, Faculty of Science, Københavns Universitet

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). (log2 ).

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:

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010