An O(n log n) algorithm for maximum st-flow in a directed planar graph
January 4, 2006
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 residuals-to-t path.
Proceedings of the Symposium of Discrete Algorithms (SODA), Miami, Florida, 2006.
[ doi ] [ pdf for full version ]
