2006 · 27 citations · 29 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationAlgorithm AnalysisCombinatorial OptimizationGraph AlgorithmsGraph TheoryNetwork Flow AlgorithmsShortest Path AlgorithmsMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsPlanar Graph AlgorithmsShortest Path In Directed GraphsShortest Path In Planar GraphsSingle-source Shortest Paths
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.
29
A new approach to the maximum-flow problem
Andrew V. Goldberg, Robert E. Tarjan · Journal of the ACM · 1988 · 1.9K citations · Full text
Claude Berge · Proceedings of the National Academy of Sciences · 1957 · 574 citations · Full text
Beyond the flow decomposition barrier
Andrew V. Goldberg, Satish Rao · Journal of the ACM · 1998 · 474 citations · Full text