アイテム詳細

要旨

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).