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

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. 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 network flow, maximum flow, graph algorithm, scaling, preflow-push algorithm, current-edge problem, dynamic tree. 68P05, 68Q20, 68Q22, 68Q25, 68