|
A fast and simple algorithm for the maximum flow problem R.K. Ahuja and J.B. Orlin, Operations Research 37, 748-759, 1989 We present a simple sequential algorithm for the maximum flow problem on a network with n nodes, m arcs, and integer arc capacities bounded by U. Under the practical assumption that U is polynomially bounded in n, our algorithm runs in time $O(nm+n^{2}\log \ n)$. This result improves the previous best bound of $O(nm\ \log (n^{2}/m))$, obtained by Goldberg and Tarjan, by a factor of log n for networks that are both nonsparse and nondense without using any complex data structures. We also describe a parallel implementation of the algorithm that runs in $O(n^{2}\log \, U\,\log \,p)$ time in the PRAM model with EREW and uses only p processors where p = [m/n]. |