Answers are grounded in this paper and cite their sources.
Recently, Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in O(n³ ) 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(nmlog (n² /m) on m-arc networks. Ahuja and Orlin developed a variant of Goldberg’s algorithm that uses scaling and runs in O(nm + (n² 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² log U/log log U) is obtained by using a nonconstant scaling factor. Second, an even better bound of O(nm + n² (log U)1/2 ) 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(nmlog ((n / m)(log U)^1 / 2 + 2)). This result shows that the combined use of three different techniques, results in speed not obtained by using any of the techniques alone. The above bounds are all for a unit-cost random access machine. Also considered is a semilogarithmic computation model in which the bounds increase by an additive term of O(mlog ₙ U), which is the time needed to read the input in the model.
No takes yet. Share an insight, caveat, or question.
Ahuja et al. (1989) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: