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
Other identifiers:
Scopus: 2-s2.0-0031212053

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

Rate this document:

Rate this document:
(Not yet reviewed)