A Fast and Simple Algorithm for the Maximum Flow Problem
Operations Research · 1989 · Volume 37 · Issue 5
Abstract
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 ⌉.
Keywords
networks/graphs, flow algorithms: fast and simple algorithm for the maximum flow problem
Enable JavaScript for citation tools and additional paper interactions.