Breaking the O(n^2.5) Deterministic Time Barrier for Undirected Unit-capacity Maximum Flow
Duan, R. · Max Planck Digital Library · 2013
This paper gives the first o(n^{2.5}) deterministic algorithm for the maximum flow problem in any undirected unit-capacity graph with no parallel edges. In an n-vertex, m-edge graph with maximum flow value v, our running time is \\tilde{O}(n^{9/4}v^{1/8})=\\tilde{O}(n^{2.375}). Note that v≤q n for simple unit-capacity graphs. The previous deterministic algorithms [Karger and Levine 1998] achieve O(m+nv^{3/2}) and O(nm^{2/3}v^{1/6}) time bound, which are both O(n^{2.5) for dense simple graphs and v=\\Theta(n).