On the parallel implementation of Goldberg's maximum flow algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the parallel implementation of Goldberg's maximum flow algorithm

Full text

Pdf (931 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, United States

Pages: 168 - 177

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Richard J. Anderson
João C. Setubal

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 103, Citation Count: 6

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/140901.140919 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.

	AG91	F. Alizadeh and A. V. Goldberg. Experiments with the Push-Relabel Method for the Maximum Flow Problem on a Connection Machine. Paper presented at the DIMACS Implementation Challenge Workshop, 1991.
	AS92	R.J. Anderson and :I. C. Setubal. Goldberg~s Algorithm for Maximum Flow in Perspective: a Computational Study. Submitted for inclusion in the DI- MACS Implementation Challenge Workshop Proceedings, 1992.
	BMPT91	Egon Balas , Donald Miller , Joseph Pekny , Paolo Toth, A parallel shortest augmenting path algorithm for the assignment problem, Journal of the ACM (JACM), v.38 n.4, p.985-1004, Oct. 1991 [doi>10.1145/115234.115349]
	CM89	J. Cheriyan , S. N. Maheshwari, Analysis of preflow push algorithms for maximum network flow, SIAM Journal on Computing, v.18 n.6, p.1057-1086, Dec. 1989 [doi>10.1137/0218072]
	DM89	U. Derigs and W. Meier. Implementing Goldberg's Max-Flow Algorithm a Computational Investigation. ZOR Methods and Models of Operation.s Research, 33:383-403, 1989.
	Din70	E.A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in a Network With Power Estimation. Soviet Math. Dokl., 11:1277-1280, 1970.
	Gol87	A.V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. Ph. D. dissertation, Massachussetts Institute of Technology, Cambridge, Mass., Jan. 1987.
	GT88	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 [doi>10.1145/48014.61051]
	GG88	D. Goldfarb and M. Grigoriadis. A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow. Annals of Operations Research, 13:83-123, 1988.
	Law76	E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976.
	PS82	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	Tar83	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

CITED BY 6

	Umakishore Ramachandran , Gautam Shah , Anand Sivasubramaniam , Aman Singla , Ivan Yanasak, Architectural mechanisms for explicit communication in shared memory multiprocessors, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.62-es, December 04-08, 1995, San Diego, California, United States
	B. Narendran , Renato De Leone , Prasoon Tiwari, An implementation of the &egr;-relaxation algorithm on the CM-5, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.183-192, June 30-July 02, 1993, Velen, Germany
	Aniruddha S. Vaidya , Anand Sivasubramaniam , Chita R. Das, Performance benefits of virtual channels and adaptive routing: an application-driven study, Proceedings of the 11th international conference on Supercomputing, p.140-147, July 07-11, 1997, Vienna, Austria
	Sanjeev Kumar , Michael Chu , Christopher J. Hughes , Partha Kundu , Anthony Nguyen, Hybrid transactional memory, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Aniruddha S. Vaidya , Anand Sivasubramaniam , Chita R. Das, Impact of Virtual Channels and Adaptive Routing on Application Performance, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.223-237, February 2001
	Rodrigo Fernandes de Mello , Evgueni Dodonov , Ricardo Bertagna , Luciano Jose Senger, Extracting and predicting the communication behaviour of parallel applications, International Journal of Parallel, Emergent and Distributed Systems, v.24 n.3, p.225-242, June 2009