A new approach to the maximum flow problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new approach to the maximum flow problem

Full text

Pdf (983 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 136 - 146

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

A V Goldberg	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
R E Tarjan	Computer Science Department, Princeton University, Princeton, NJ and AT&T Bell Laboratories, Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 44, Downloads (12 Months): 297, Citation Count: 33

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/12130.12144 What is a DOI?

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	Baruch Awerbuch, An efficient network synchronization protocol, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.522-525, December 1984 [doi>10.1145/800057.808722]
	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).
	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.
	4	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]
	5	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	6	L .R . Ford, Jr. and D. R. Fulkerson, "Maximal flow through a network," Can. J. Math. 8 (1956), 399-404.
	7	L .R . Ford, Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, N J, 1962.
	8	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]
	9	H.N. Gabow, "Scaling algorithms for network problems," Proc. 24th IEEE Syrup. on Found. of Comput. Science (1983), 248-258.
	10	Z. Galil, "An O(V 6/s E 2/3) algorithm for the maximal flow problem," Acta Informatica 14 (1980), 221-242.
	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.
	12	A. V. Goldberg, "A new max-flow rithm," Tech. Mere. MIT/LCS/TM-Laboratory for Computer Science, Mass. of Tech., Cambridge, MA, 1985.
	13	A. V. Karzanov, "Determining the maximal flow in a network by the method preflows," Soviet Math. Dokl. 15 (1974), 437.
	14	E. L. Lawler, Combinatorial Optimization: works and Matroids, Holt, Rinehart, and ton, New York, NY, 1976.
	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.
	16	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	17	J. C. Picard and H. D. Ratliff, "Minimum cuts and related problems," Networkn (1975), 357-370.
	18	Yossi Shiloach, An O($n\cdot I \log^2 I$) maximum-flow algorithm, Stanford University, Stanford, CA, 1978
	19	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]
	20	D. D. Sleator, "An O(nmlogn) algorithm for maximum network flow," Tech. STAN-CS-80-831, Computer Science Stanford University, Stanford, CA, 1980.
	21	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]
	22	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]
	23	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	24	R. E. Tarjan, "A simple version Karzanov's blocking flow algorithm," tiona Research Lett. 2 (1984), 265-268.

CITED BY 33

	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
	Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Dimitrios Kagaris , Spyros Tragoudas, Maximum independent sets on transitive graphs and their applications in testing and CAD, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.736-740, November 09-13, 1997, San Jose, California, United States
	A. Olson , K. G. Shin, Fault-Tolerant Clock Synchronization in Large Multicomputer Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.912-923, September 1994
	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
	J. S. Mitchell, On maximum flows in polyhedral domains, Proceedings of the fourth annual symposium on Computational geometry, p.341-351, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Philip K. McKinley , Jane W. S. Liu, Multicast tree construction in bus-based networks, Communications of the ACM, v.33 n.1, p.29-42, Jan. 1990
	Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States
	Norman D. Curet , Jason DeVinney , Matthew E. Gaston, An efficient network flow code for finding all minimum cost s-t cutsets, Computers and Operations Research, v.29 n.3, p.205-219, March 2002
	Donald B. Johnson, Parallel algorithms for minimum cuts and maximum flows in planar networks, Journal of the ACM (JACM), v.34 n.4, p.950-967, Oct. 1987
	Noriko Imafuji , Masaru Kitsuregawa, Effects of maximum flow algorithm on identifying web community, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA
	Baruch Shieber , Shlomo Moran, Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: maximum matchings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.282-292, August 11-13, 1986, Calgary, Alberta, Canada
	James Hwang , Abbas El Gamal, Optimal replication for min-cut partitioning, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.432-435, November 1992, Santa Clara, California, United States
	Anoop Gupta , Andrew Tucker , Shigeru Urushibara, The impact of operating system scheduling policies and synchronization methods of performance of parallel applications, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.120-132, May 1991
	Lintao Zhang , Conor F. Madigan , Matthew H. Moskewicz , Sharad Malik, Efficient conflict driven learning in a boolean satisfiability solver, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Edgar Knapp, An exercise in the formal derivation of parallel programs: maximum flows in graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.2, p.203-223, April 1990
	Boris V. Cherkassky , Andrew V. Goldberg , Paul Martin , Joao C. Setubal , Jorge Stolfi, Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms, Journal of Experimental Algorithmics (JEA), 3, p.8-es, 1998
	Cheol-Hoon Lee , Dongmyun Lee , Myunghwan Kim, Optimal Task Assignment in Linear Array Networks, IEEE Transactions on Computers, v.41 n.7, p.877-880, July 1992
	Anoop Gupta , Wolf-Dietrich Weber, Cache Invalidation Patterns in Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.41 n.7, p.794-810, July 1992
	P. Agrawal , A. Ng, Computing Network Flow on a Multiple Processor Pipeline, IEEE Transactions on Parallel and Distributed Systems, v.5 n.6, p.653-658, June 1994
	Cheol-Hoon Lee , Kang G. Shin, Optimal Task Assignment in Homogeneous Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.119-129, February 1997
	Antonio Sedeño-Noda , Carlos González-Martín , Sergio Alonso, A generalization of the scaling max-flow algorithm, Computers and Operations Research, v.31 n.13, p.2183-2198, November 2004
	Jinquan Dai , Bo Huang , Long Li , Luddy Harrison, Automatically partitioning packet processing applications for pipelined architectures, ACM SIGPLAN Notices, v.40 n.6, June 2005
	Chi-Chung Hui , Samuel T. Chanson, Allocating Task Interaction Graphs to Processors in Heterogeneous Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.908-925, September 1997
	R. Cerulli , M. Gentili , A. Iossa, Efficient preflow push algorithms, Computers and Operations Research, v.35 n.8, p.2694-2708, August, 2008
	Stefan Irnich, Undirected postman problems with zigzagging option: A cutting-plane approach, Computers and Operations Research, v.35 n.12, p.3998-4009, December, 2008
	Daniel A. Spielman , Nikhil Srivastava, Graph sparsification by effective resistances, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Andrew Goldberg , Robert Tarjan, Finding minimum-cost circulations by canceling negative cycles, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.388-397, May 02-04, 1988, Chicago, Illinois, United States
	Youssef Saab, A Fast and Effective Algorithm for the Feedback Arc Set Problem, Journal of Heuristics, v.7 n.3, p.235-250, May 2001
	Jia Yu , Jingnan Yao , Laxmi Bhuyan , Jun Yang, Program mapping onto network processors by recursive bipartitioning and refining, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Nikos Paragios , Ramin Zabih, Editorial: Discrete optimization in computer vision, Computer Vision and Image Understanding, v.112 n.1, p.1-2, October, 2008
	Hyun Chul Lee , Allan Borodin , Leslie Goldsmith, Extracting and ranking viral communities using seeds and content similarity, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA
	Antonin Chambolle , Jérôme Darbon, On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows, International Journal of Computer Vision, v.84 n.3, p.288-307, September 2009