A V Goldberg
R E Tarjan
- 1.B. Awerbuch, "An efficient network synchronization protocol," Proc. 16th ACM Syrup. on Theory of Computing (1984), 522-525. Google Scholar
Digital Library
- 2.R.V. Cherkasky, "Algorithm of construction of maximal flow in networks with complexity of O( V 2 ~/~) operations," Mathematical Methods of Solution of Economical Problems 7 (1977), 112-125 (in Russian).Google Scholar
- 3.E. A. Dinic, "Algorithm for solution of a problem of maximum flow in networks with power estimation," Soviet Math. Dokl. 11 (1980), 1277-1280.Google Scholar
- 4.J. Edmonds and R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems," J. Assoc. Comput. Math. 19 (1972), 248-264. Google ScholarDigital Library
- 5.S. Even, Graph Algorithms, Computer Science Press, Potomac, MD, 1979. Google ScholarDigital Library
- 6.L .R . Ford, Jr. and D. R. Fulkerson, "Maximal flow through a network," Can. J. Math. 8 (1956), 399-404.Google ScholarCross Ref
- 7.L .R . Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, N J, 1962.Google Scholar
- 8.S. Fortune and J. Wylie, "Parallelism in random access machines," Pro~. 10th ACM Syrup. on Theory of Computing (1978), 114-118. Google ScholarDigital Library
- 9.H.N. Gabow, "Scaling algorithms for network problems," Proc. 24th IEEE Syrup. on Found. of Comput. Science (1983), 248-258.Google Scholar
- 10.Z. Galil, "An O(V 6/s E 2/3) algorithm for the maximal flow problem," Acta Informatica 14 (1980), 221-242.Google ScholarDigital Library
- 11.Z. Galil and A. Naamad, "An O(EVlog 2 V) algorithm for the maximal flow problem," J. CompuL System SoL 21 (1980), 203-217.Google ScholarCross Ref
- 12.A. V. Goldberg, "A new max-flow rithm," Tech. Mere. MIT/LCS/TM-Laboratory for Computer Science, Mass. of Tech., Cambridge, MA, 1985.Google Scholar
- 13.A. V. Karzanov, "Determining the maximal flow in a network by the method preflows," Soviet Math. Dokl. 15 (1974), 437.Google Scholar
- 14.E. L. Lawler, Combinatorial Optimization: works and Matroids, Holt, Rinehart, and ton, New York, NY, 1976.Google Scholar
- 15.V. M. Malhotra, M. Pramodh Kumar, N. Malacshwart, "An O(IVy) algorithm finding maximum flows in networks," Proce~8. Lett 7 (1978), 277-278.Google ScholarCross Ref
- 16.C. H. Papadimitrion and K. Steiglitz, binatorial Optimization: Algorithma and plezity, Prentice-Hall, Englewood Cliffs, 1982. Google ScholarDigital Library
- 17.J. C. Picard and H. D. Ratliff, "Minimum cuts and related problems," Networkn (1975), 357-370.Google Scholar
- 18.Y. Shiloaeh, "An O(n" I log 2I) maximumflow algorithm," Teeh. Rep. STAN-802, Computer Science Dept., Stanford University, Stanford, CA, 1978. Google ScholarDigital Library
- 19.Y. Shiloach and V. Vishldn, "An O(n21ogn) parallel max-flow algorithm," Y. Algorithms (1982), 128-146. Google ScholarDigital Library
- 20.D. D. Sleator, "An O(nmlogn) algorithm for maximum network flow," Tech. STAN-CS-80-831, Computer Science Stanford University, Stanford, CA, 1980.Google Scholar
- 21.D.D. Sleator and R. E. Tarjan, "A data ture for dynamic trees," J. Comput. Sci. 24 (1983), 362-391. Google ScholarDigital Library
- 22.D. D. Sleator and R. E. Tarjan, adjusting binary search trees," Y. Assoc. put. Math. 32 (1985), 652-686. Google ScholarDigital Library
- 23.R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Math., Philadelphia, PA, 1983. Google ScholarDigital Library
- 24.R. E. Tarjan, "A simple version Karzanov's blocking flow algorithm," tiona Research Lett. 2 (1984), 265-268.Google Scholar
Index Terms
- A new approach to the maximum flow problem
Recommendations
A new strategy for the undirected two-commodity maximum flow problem
We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a ...
The maximum concurrent flow problem
The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of entities can send and receive flow concurrently. The ratio of the flow supplied between a pair of entities to the predefined demand for that pair is ...
A strongly polynomial algorithm for the minimum maximum flow degree problem
AbstractLet us consider a network flow respecting arc capacities and flow conservation constraints. The flow degree of a node is sum of the flow entering and leaving it. We study the problem of determining a flow that minimizes the maximum ...
Highlights- Introduction of a new formulation for the minimum maximum flow degree problem.
- ...
Comments