The authors 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, the present algorithm runs in time O(nm+n2logn). This result improves the previous best bound of O(nmlog(n2/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. The authors also describe a parallel implementation of the algorithm that runs in O(n2logUlogp) time in the PRAM model with EREW and uses only p processors where p=⌈m/n⌉.
