Abstract.
In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter \(\epsilon\) such that \(0<\epsilon\) , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ \(\epsilon\) factor. The time bounds for both query and update for our algorithm is O( \epsilon -1 n 2/3 log 2 n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received January 1995; revised February 1997.
Rights and permissions
About this article
Cite this article
Klein, P., Subramanian, S. A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs . Algorithmica 22, 235–249 (1998). https://doi.org/10.1007/PL00009223
Issue Date:
DOI: https://doi.org/10.1007/PL00009223