A new approach to the maximum-flow problem

ABSTRACT

All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an O(n3) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O(nm log(n2/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in O(n2log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses n processors but requires O(n2) space.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AHUJA, R. K. AND ORLIN, J.B. A fast and simple algorithm for the maximum flow problem. Tech. Rep. 1905-87, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Mass., 1987.
	1a	AHUJA, R. K., ORLIN, J. B., AND TARJAN, R.E. Improved time bounds for the maximum flow problem. Unpublished mansucript.
	2	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	2a	CHERIYAN, J., AND MAHESHWARI, S. N. Analysis of preflow push algorithms for maximum network flow. Department of Computer Science and Engineering, Indian Institute of Tech., New Delhi, India, 1987.
	3	CHERKASKY, R.V. An algorithm for constructing maximal flows in networks with complexity of O(V2x/E) operations. Math. Methods Solution Econ. Probl. 7 (1977), 112-125. (In Russian.)
	4	DINIC, E.A. Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11 (1970), 1277-1280.
	5	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	6	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	7	FORD, L. R., JR., AND FULKERSON, D.R. Maximal flow through a network. Can. J. Math. 8 (1956), 399-404.
	8	FORD, L. R., JR., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.j., 1962.
	9	Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
	10	Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
	11	GALIL, Z. An 0(VS/3E2/3) algorithm for the maximal flow problem. Acta Inf. 14 (1980), 221-242.
	12	GALIL, Z., AND NAAMAD, A. An O(EV log2V) algorithm for the maximal flow problem. J. Comput. Syst. Sci. 21 (1980), 203-217.
	13	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	14	GOLDBERG, A. V. A new max-flow algorithm. Tech. Rep. MIT/LCS/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., 1985.
	15	A. V. Goldberg, EFFICIENT GRAPH ALGORITHMS FOR SEQUENTIAL AND PARALLEL COMPUTERS, Massachusetts Institute of Technology, Cambridge, MA, 1987
	16	A V Goldberg , R E Tarjan, A new approach to the maximum flow problem, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.136-146, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12144]
	17	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
	18	KARZANOV, A.V. Determining the maximal flow in a network by the method of preflows. Sov. Math. Dokl. 15 (1974), 434-437.
	19	LAWLER, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976.
	20	LEISERSON, C., AND MAGGS, B. Communication-efficient parallel graph algorithms. In Proceedings of the International Conference on Parallel Processing. IEEE Computer Society Press, Silver Spring, Md., 1986, pp. 861-868.
	21	MALHOTRA, V. M., PRAMODH KUMAR, M., AND MAHESHWARI, S.N. An O(I V I3) algorithm for finding maximum flows in networks. Inf. Process. Lett. 7 (1978), 277-278.
	22	OGIELSKI, A. T. Integer optimization and zero-temperature fixed point in Ising random-field systems. Phys. Rev. Lett. 57 (1986), 1251-1254.
	23	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	24	PICARD, J. C., AND RATLIFF, H. O. Minimum cuts and related problems. Networks 5 (1975), 357-370.
	25	Yossi Shiloach, An O($n\cdot I \log^2 I$) maximum-flow algorithm, Stanford University, Stanford, CA, 1978
	26	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
	27	SLEATOR, D.D. An O(nm log n) algorithm for maximum network flow. Tech. Rep. STAN-CS- 80-831, Computer Science Dept., Stanford Univ., Stanford, Calif., 1980.
	28	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	29	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
	30	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	31	TAP.JAN, R.E. A simple version of Karzanov's blocking flow algorithm. Oper. Res. Lett. 2 (1984), 265-268.