00177817

a

00177817 Cheriyan, Joseph Hagerup, Torben Mehlhorn, Kurt Can a maximum flow be computed in $o(nm)$ time? Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 235-248 (1990). 1990 Berlin etc.: Springer-Verlag EN maximum flow optimal parallel algorithms Zbl 0758.00017 Summary: [For the entire collection see Zbl 0758.00017.] We show that a maximum flow in a network with $n$ vertices can be computed deterministically in $O(n\sp 3/\log n)$ time on a uniform-cost RAM. For dense graphs, this improve the previous best bound of $O(n\sp 3)$. The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is $O(n\sp{8/3}(\log n)\sp{4/3})$, in constrast 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\sp{3/2} m\sp{1/2} (\log n)\sp{3/2} + n\sp 2(\log n)\sp 2)$ flow operations with high probability. Specializing to the case in which all capacities are integers bounded by $U$, we show that a maximum flow can be computed using $O(n\sp{3/2} m\sp{1/2}+ n\sp 2(\log U)\sp{1/2})$ flow operations. Finally, we argue that several of our results yield optimal parallel algorithms.