Faster Shortest-Path Algorithms for Planar Graphs

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 requiring O(n4/3 log(nL)) time, where L is 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.


Published in:
J. Comput. Syst. Sci., 55, 1, 3-23
Year:
1997
Keywords:
Other identifiers:
Scopus: 2-s2.0-0031212053
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)