August 5, 2012

 

Max flows in O(nm) time or better.

This is my only web page devoted to a single paper. 

The paper gives a new algorithm that solves the max flow problem in O(nm) time, resolving a long standing conjecture.  The paper also shows how to solve the max flow problem in O(n2/log n) time in the case that m = O(n).  There are some other speedups in special cases.

Paper.