A Fast and Simple Algorithm for the Maximum Flow Problem

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