2011 · 54 citations · 33 references
ComputingComputer ScienceAlgorithmsComputational GeometryParallel AlgorithmsCombinatorial OptimizationGraph AlgorithmsNetwork Flow AlgorithmsNetwork FlowsSublinear AlgorithmsDirected GraphsMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsNetwork Flow ProblemsPlanar Graph AlgorithmsPlanar Graphs
We give an O(n log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.
33
Efficient Algorithms for Shortest Paths in Sparse Networks
D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text