Max flows in O(nm) time, or better

By James B. Orlin. Symposium on the Theory of Computing, 2013

445 citations recorded by the source corpus.

In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m31/16 log2 n) time. In the case that m = O(n1.06), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm logm/(n log n)n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n2/ log n).

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/7434ad6adff98e18094db11d7f41fb4ff6016f53

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

Citations in the corpus

Advances in quantum cryptography (2019, unknown): “The optimal multi-path routing of is provided by the solution of the maximum flow problem, which can be found in O(|P |× |E|) time by using Orlin’s algorithm [639].”
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, background): “The current fastest “strongly” polynomial running time for solving this problem is O(nm) [33].”