|
Improved time bounds for the maximum flow problem R.K. Ahuja, J.B. Orlin, and R.E. Tarjan, IAM Journal of Computing 18, 939-954, 1989 A new approach is proposed to the maximum network flow problem. The approach yields a very simple algorithm running O(n-cubed) time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of O(nm log (n-squared/m)) on m-edge networks. A variant of the algorithm is developed that uses scaling and runs in O(nm + (n-sq) log U) time on networks with integer edge capacities bounded by U. This paper obtains a modification of the Ahuja-Orlin algorithm with a running time of O(nm + (n-sq) (log U)/(log log u). The use of dynamic trees in this algorithm further reduces the time bound on O(nm log (n log U/mlog log U + 2)). This result demonstrates that the combined use of scaling and dynamic trees results in speed not obtained by using either technique alone. |