- 1 DINIC, E.A. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soy. Math. Dokl. 11 (1970), 1277-1280.Google Scholar
- 2 EDMONDS, J. Paths, trees and flowers. Canadian J. Math. 17 (1965), 449 467.Google Scholar
- 3 EDMONDS, J., AND KARP, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. Combinatorial Structures and Their Applications. Gordon and Breach, New York, 1970, pp. 93-96 (abstract presented at Calgary International Conference on Combinatorial Structures and Their Applications, June 1969).Google Scholar
- 4 EDMONDS, J., AND FULKERSON, D. R. Bottleneck extrema. RAND Corp. Memorandum RM-5375-PR (Jan. 1968).Google Scholar
- 5 FORD, L. I{., AND FULKERSON, I). R. Flows in Networks. Princeton U. Press, Princeton, N.J., 1962.Google Scholar
- 6 FULKERSON, D. ll. On the equivalence of the capacity-constrained transshipment problem and the Hitchcock problems. RAND Corp. Memorandum RM-2480 (Jan. 1960).Google Scholar
- 7 WAGNER, H.M. On a class of capacitated transportation problems. Manag. Sci. 5 (1959), 304 318.Google Scholar
Index Terms
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Recommendations
Theoretical improvements in algorithmic efficiency for network flow problems
Combinatorial optimization - Eureka, you shrink!This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem and the general minimum-cost flow problem. Upper bounds on the number of steps in these algorithms are derived, and are shown to improve on the upper ...
Comments