research-article

A near-linear time algorithm for computing replacement paths in planar directed graphs

Authors:

Yuval Emek,

David Peleg,

Liam RodittyAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 428 - 435

Published: 20 January 2008 Publication History

Get Access

Abstract

Let G = (V(G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a shortest path from s to t that avoids e. The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O (mn + n² log n), where n = |V(G)| and m = |E(G)|.

The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [21, 13] repeatedly computes the replacement paths from s to t. Its running time is O(kn(m + n log n)). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [16] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph.

In this paper we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O(n log³ n) time. This result immediately improves the running time of the two applications mentioned above by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [12] that supports multi-source shortest paths queries in planar directed graphs in logarithmic time.

Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time Õ(h), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.

References

[1]

T. H. Cormen, C. E. Leiserson and R. L. Rivest. Introduction to Algorithms. The MIT Press, 1990.

Abstract

References

Cited By

Index Terms

Recommendations

A near-linear-time algorithm for computing replacement paths in planar directed graphs

Replacement paths and k simple shortest paths in unweighted directed graphs

A linear time algorithm for the induced disjoint paths problem in planar graphs

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations