The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
An $o(n^3)$-Time Maximum-Flow Algorithm
Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn,
Pages. 1144-1170
Abstract We show that a maximum flow in a network with $n$ vertices can be computed deterministically in $O(n^3/ log n)$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3)$.\indent The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n^{8/3}(log n)^{4/3}$, in contrast with $Omega(nm)$ flow operations for all previous algorithms, where $m$ denotes the number of edges in the network. A randomized version of our algorithm executes $O(n^{3/2}m^{1/2}log n +n^2(log n)^2/log(2+n(log n)^2/m))$ flow operations with high probability.\indent For the special case in which all capacities
are integers bounded by $U$, we show that a maximum flow can be computed deterministically using $O(n^{3/2}m^{1/2}+n^2(log
U)^{1/2}+log U)$ flow operations and $O(min{nm, n^3/ log n}+n^2(log U)^{1/2}+log U)$ time. We finally argue that several of our results yield parallel algorithms with optimal speedup.
Contents 1. Introduction
2. Definitions and notation
3. The incremental generic algorithm
4. The incremental excess scaling algorithm
5. The incremental wave scaling algorithm
6. Solutions to the current-edge problem
7. The incremental strongly polynomial algorithm
8. The extended current-edge problem and PTR events
9. Parallel algorithm
10. Open problems
Key words network flow, maximum flow, graph algorithm, scaling, preflow-push algorithm, current-edge problem, dynamic tree.
Mathmatical Subject Classification 68P05, 68Q20, 68Q22, 68Q25, 68