## Abstract

Recently, A.V. Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in O(n^{3}) time on n-vertex networks. Incorporation of the dynamic tree data structure of D.D. Sleator and R.E. Tarjan yields a more complicated algorithm with a running time of O(nm log (n^{2}/m)) on m-arc networks. R.K. Ahuja and J.B. Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in O(nm + n^{2} log U) time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of O(nm + n^{2} log U/log log U) is obtained by using a nonconstant scaling factor. Second, an even better bound of O(nm + n^{2}(log U)^{HLF} is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to O(nm log ((n/m)(log U)^{HLF} + 2)).

Original language | English (US) |
---|---|

Pages (from-to) | 939-954 |

Number of pages | 16 |

Journal | SIAM Journal on Computing |

Volume | 18 |

Issue number | 5 |

DOIs | |

State | Published - 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)