An O(n log n) algorithm for maximum st-flow in a directed planar graph
April 4, 2009
Glencora Borradaile and Philip Klein
We give the first correct O(n log n) algorithm for finding a maximum st-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s-to-t path.
Journal of the ACM, 56(2), 2009.
[ doi ]
