An Õ(n2) algorithm for minimum cuts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Õ(n²) algorithm for minimum cuts

Full text

Pdf (920 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 757 - 765

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

David R. Karger
Clifford Stein

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 67, Citation Count: 15

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

	App92	D. Applegate, 1992. personal communication.
	CHM90	Joseph Cheriyan , Torben Hagerup , Kurt Mehlhorn, Can a maximum flow be computed in o(nm) time?, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.235-248, July 1990, Warwick University, England
	DFJ54	G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson. Solution of a large-scale traveling-salesman problem. Operations Research, 2:393-410, 1954.
	EFS56	P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, pages 117-199, 1956.
	EK72	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]
	FF56	L.R. Ford and D. R. Fulkerson. Maximal flow through a network. Canad. J. Math., 8:399-404, 1956.
	Gab91	Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
	GH61	R.E. Gomory and T. C. Hu. Multiterminal network flows. J. SIAM, 9:551- 570, 1961.
	GP85	Z. Galil and V. Pan. Improved processor bounds for algebraic and combinatorial problems in TiNC. Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 490-495, 1985. To appear in Journal of the A CM.
	GSS82	L. Goldschlager, R. Shaw, and J. Staples. The maximum flow problem is log-space complete for :P. Theoretical Computer Science, 21:105-111, 1982.
	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]
	HO92	Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a graph, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.165-174, September 1992, Orlando, Florida, United States
	FF62	L.R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.
	Kar93	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	KPST91	P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
	KRT92	V. King , S. Rao , R. Tarjan, A faster deterministic maximum flow algorithm, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.157-164, September 1992, Orlando, Florida, United States
	KT86	A.V. Karzanov and E. A. Timofeev. Efficient algorithm for finding all minimal edge cuts of a non-oriented graph. Kibernetika, 22:8-12, 1986. Translation in Cybernetics 22, 1986, pages 156-162.
	KUW86	R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
	LLKS85	E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, and D.B. Shmoys, editors. The Traveling Salesman Problem. John Wiley and Sons, 1985.
	Mat87	D.W. Matula. Determining edge connectivity in o(nm). Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 249-251, October 1987.
	MVV87	K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
	NI92	Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
	NV91	D. Naor and V. Vazirani. Representing and enumerating edge connectivity cuts in TiNC. Proceedings of the Second Workshop on Algorithms and Data Structures, pages 273-285, 1991. Published as Lecture Notes in Computer Science 519, Springer- Verlag.
	Pod73	V.D. Podderyugin. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern., 2:136, 1973.
	PQ82	J.C. Picard and M. Querayne. Selected applications of minimum cuts in networks. INFOR., 20:394-422, November 1982.
	PR90	M. Padberg , G. Rinaldi, An efficient algorithm for the minimum capacity cut problem, Mathematical Programming: Series A and B, v.47 n.1, p.19-36, May 1990 [doi>10.1007/BF01580850]
	PW92	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 [doi>10.1145/167088.167201]
	Ram87	V. Ramachandran. Flow value, minimum cuts and maxmium flows, 1987. Unpublished manuscript.

CITED BY 15

	David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	David R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.11-17, May 29-June 01, 1995, Las Vegas, Nevada, United States
	András A. Benczúr, Augmenting undirected connectivity in RNC and in randomized Õ(n³) time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.658-667, May 23-25, 1994, Montreal, Quebec, Canada
	David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Mechthild Stoer , Frank Wagner, A simple min-cut algorithm, Journal of the ACM (JACM), v.44 n.4, p.585-591, July 1997
	András A. Benczúr , David R. Karger, Augmenting undirected edge connectivity in Õ(n2) time, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.500-509, January 25-27, 1998, San Francisco, California, United States
	Karin Hogstedt , Doug Kimelman , V T Rajan , Tova Roth , Mark Wegman, Graph cutting algorithms for distributed applications partitioning, ACM SIGMETRICS Performance Evaluation Review, v.28 n.4, p.27-29, March 2001
	David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada
	David R. Karger , Rajeev Motwani, Derandomization through approximation: an NC algorithm for minimum cuts, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.497-506, May 23-25, 1994, Montreal, Quebec, Canada
	Chandra S. Chekuri , Andrew V. Goldberg , David R. Karger , Matthew S. Levine , Cliff Stein, Experimental study of minimum cut algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.324-333, January 05-07, 1997, New Orleans, Louisiana, United States
	Hiroshi Nagamochi , Toshihide Ibaraki, Graph connectivity and its augmentation: applications of MA orderings, Discrete Applied Mathematics, v.123 n.1-3, p.447-472, 15 November 2002
	David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996
	David R. Karger , Ray P. Tai, Implementing a fully polynomial time approximation scheme for all terminal network reliability, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.334-343, January 05-07, 1997, New Orleans, Louisiana, United States
	Sangho Kim , Betsy George , Shashi Shekhar, Evacuation route planning: scalable heuristics, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington