A faster deterministic maximum flow algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A faster deterministic maximum flow algorithm

Full text

Pdf (702 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms table of contents

Orlando, Florida, United States

Pages: 157 - 164

Year of Publication: 1992

ISBN:0-89791-466-X

Authors

V. King
S. Rao
R. Tarjan

Sponsors

SIAM : Society for Industrial and Applied Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 52, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

We describe a deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time O(mn + n2+&egr;, for any constant &egr;. This improves upon Alon's 1989 bound of O(mn + n8/3log n) [A] and gives an O(mn) deterministic algorithm for all m > n1+&egr;. Thus it extends the range of m/n for which an O(mn) algorithm is known, and matches the 1988 algorithm of Goldberg and Tarjan [GT] for smaller values of m/n.

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.

	AMO	R. K. Ahuja , T. L. Magnanti , J. B. Orlin, Network flows, Optimization, Elsevier North-Holland, Inc., New York, NY, 1989
	A	N. Alan, "Generating Pseudo-Random Permutations and Maximum Flow Algorithms,~ manuscript.
	CH	J. Cheriyan and T. Hagerup, "A Randomized Maximum-Flow Algofithmf Proc.iEEE FOGS (1989), 118-123.
	CHM	J. Cheriyan, T. Hagerup, K. Mehlhorn, "Can a Maximum Flow be Computed in o(nm) Time7' ICALP (lo9o)
	GT	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]
	GTT	A.V. Goldberg, E. Ta~dos, aad R. E. Tarjaz, 'Network flow algorithms,' in Paths, Flows, and VLSI- Layout, B. Korte, L. Lovlsz, H. J. Pr6mel, and A. Schriver, eds., Springer-Verlag, Berlin, (1990), 101-164.
	ST	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]

CITED BY 8

	Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States
	Michael K. Reiter , Stuart G. Stubblebine, Authentication metric analysis and design, ACM Transactions on Information and System Security (TISSEC), v.2 n.2, p.138-158, May 1999
	Michael K. Reiter , Stuart G. Stubblebine, Resilient Authentication Using Path Independence, IEEE Transactions on Computers, v.47 n.12, p.1351-1362, December 1998
	Michael K. Reiter , Stuart G. Stubblebine, Path independence for authentication in large-scale systems, Proceedings of the 4th ACM conference on Computer and communications security, p.57-66, April 01-04, 1997, Zurich, Switzerland
	Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany
	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States
	Cynthia A. Phillips, The network inhibition problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.776-785, May 16-18, 1993, San Diego, California, United States
	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998