Faster shortest-path algorithms for planar graphs
Henzinger MH, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.
Download (ext.)
https://doi.org/10.1006/jcss.1997.1493
[Published Version]
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Klein, Philip;
Rao, Satish;
Subramanian, Sairam
Abstract
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.
Publishing Year
Date Published
1997-08-01
Journal Title
Journal of Computer and System Sciences
Publisher
Elsevier
Volume
55
Issue
1
Page
3-23
ISSN
IST-REx-ID
Cite this
Henzinger MH, Klein P, Rao S, Subramanian S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 1997;55(1):3-23. doi:10.1006/jcss.1997.1493
Henzinger, M. H., Klein, P., Rao, S., & Subramanian, S. (1997). Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1006/jcss.1997.1493
Henzinger, Monika H, Philip Klein, Satish Rao, and Sairam Subramanian. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences. Elsevier, 1997. https://doi.org/10.1006/jcss.1997.1493.
M. H. Henzinger, P. Klein, S. Rao, and S. Subramanian, “Faster shortest-path algorithms for planar graphs,” Journal of Computer and System Sciences, vol. 55, no. 1. Elsevier, pp. 3–23, 1997.
Henzinger MH, Klein P, Rao S, Subramanian S. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences. 55(1), 3–23.
Henzinger, Monika H., et al. “Faster Shortest-Path Algorithms for Planar Graphs.” Journal of Computer and System Sciences, vol. 55, no. 1, Elsevier, 1997, pp. 3–23, doi:10.1006/jcss.1997.1493.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access