Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat, Philip N. Klein · 2013
We give simple linear-time algorithms for two problems in planar graphs: max st-flow in directed graphs with unit capacities, and multiple-source shortest paths in undirected graphs with unit lengths.