Article

Free access

Using random sampling to find maximum flows in uncapacitated undirected graphs

Author:

David R. KargerAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 240 - 249

https://doi.org/10.1145/258533.258596

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

ACM. Proceedings of the 28th ACM Symposium on Theory of Computing. ACM Press, May 1996.

Google Scholar

[2]

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

Digital Library

Google Scholar

[3]

Noga Alon, Paul Seymour, and Thomas R. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the 22r'a ACM Symposium on Theory of Computing, pages 293-299. ACM, ACM Press, May 1990.

Digital Library

Google Scholar

[4]

Andr~is A. Benczfir and David R. Karger. Approximate s-t min-cuts in t)(n2) time. In Proceedings of the 28th ACM Symposium on Theory of Computing {ACM96}, pages 47-55.

Digital Library

Google Scholar

[5]

Shimon Even. Graph Algorithms. Computer Science Press, Potomac, MD, 1979.

Digital Library

Google Scholar

[6]

Lester R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.

Crossref

Google Scholar

[7]

Lester R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, New Jersey, 1962.

Google Scholar

[8]

John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5:375-390, 1984.

Digital Library

Google Scholar

[9]

A.V. Goldberg and R. Kennedy. Global Price Updates Help. Technical Report STAN-CS-94-1509, Department of Computer Science, Stanford University, 1994. To appear in SIAM J. on Discrete Math.

Digital Library

Google Scholar

[10]

Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-1036, 1989.

Digital Library

Google Scholar

[11]

Monika Rauch Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the 27th ACM Symposium on Theory of Computing, pages 519-527. ACM, ACM Press, May 1995.

Digital Library

Google Scholar

[12]

David R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the 26th ACM Symposium on Theory of Computing, pages 648-657. ACM, ACM Press, May 1994. Submitted for publication.

Digital Library

Google Scholar

[13]

David R. Karger. Minimum cuts in near-linear time. in Proceedings of the 28th ACM Symposium on Theory of Computing {ACM96}, pages 56-63.

Digital Library

Google Scholar

[14]

David R. Karger. A randomized fully polynomial approximation scheme for the all terminal network reliability problem. SIAM Journal on Computing, 1997. To appear. A preliminary version appeared in STOC 1995.

Digital Library

Google Scholar

[15]

Phil Klein, Satish Rao, and Serge Plotkin. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th ACM Symposium on Theory of Computing, pages 682- 690. ACM, ACM Press, May 1993.

Digital Library

Google Scholar

[16]

J.C. Picard and H.D. Ratliff. Minimum cuts and related problems. Networks, 5:357-370, 1975.

Crossref

Google Scholar

[17]

Serge Plotkin, Satish Rao, and W. Smith. Shallow excluded minors and improved decompositions. In Proceedings of the 5tn Annual ACM-SIAM Symposium on Discrete Algorithms, pages 462--470. ACM-SIAM, January 1994.

Digital Library

Google Scholar

[18]

Robert E. Tarjan. Data Structures and Network Algorithms, volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, 1983.

Digital Library

Google Scholar

[19]

Mikkel Thomp. Dynamic decremental connectivity. In Proceedings of the 6th Annual ACM- SIAM Symposium on Discrete Algorithms, pages 305-313. ACM-SIAM, January 1995.

Digital Library

Google Scholar

Cited By

View all

Kathuria TLiu YSidford A(2022)Unit Capacity Maxflow in Almost $m^{4/3}$ TimeSIAM Journal on Computing10.1137/20M138352553:6(FOCS20-175-FOCS20-204)Online publication date: 18-Apr-2022
https://doi.org/10.1137/20M1383525
Liu YSidford AMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Faster energy maximization for faster maximum flowProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384247(803-814)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384247
Kathuria TLiu YSidford A(2020)Unit Capacity Maxflow in Almost Time2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00020(119-130)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00020
Show More Cited By

Index Terms

Recommendations

On flows in bidirected graphs

Bouchet conjectured that every bidirected graph which admits a nowhere-zero bidirected flow will admit a nowhere-zero bidirected 6-flow [A. Bouchet, Nowhere-zero integer flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279-292]. He proved ...
Nowhere-zero 3-flows in triangularly connected graphs

Let H"1 and H"2 be two subgraphs of a graph G. We say that G is the 2-sum of H"1 and H"2, denoted by H"1@__ __"2H"2, if E(H"1)@__ __E(H"2)=E(G), |V(H"1)@__ __V(H"2)|=2, and |E(H"1)@__ __E(H"2)|=1. A triangle-path in a graph G is a sequence of distinct ...
Nowhere-Zero Flows in Random Graphs

A nowhere-zero 3-flow in a graph G is an assignment of a direction and a value of 1 or 2 to each edge of G such that, for each vertex v in G, the sum of the values of the edges with tail v equals the sum of the values of the edges with head v. Motivated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
617
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)14

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kathuria TLiu YSidford A(2022)Unit Capacity Maxflow in Almost $m^{4/3}$ TimeSIAM Journal on Computing10.1137/20M138352553:6(FOCS20-175-FOCS20-204)Online publication date: 18-Apr-2022
https://doi.org/10.1137/20M1383525
Liu YSidford AMakarychev KMakarychev YTulsiani MKamath GChuzhoy J(2020)Faster energy maximization for faster maximum flowProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384247(803-814)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3357713.3384247
Kathuria TLiu YSidford A(2020)Unit Capacity Maxflow in Almost Time2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00020(119-130)Online publication date: Nov-2020
https://doi.org/10.1109/FOCS46700.2020.00020
Duan RKhanna S(2013)Breaking the o(n2.5) deterministic time barrier for undirected unit-capacity maximum flowProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627901(1171-1179)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627901
Azar YMdry AMoscibroda TPanigrahi DSrinivasan A(2011)Maximum bipartite flow in networks with adaptive channel widthTheoretical Computer Science10.1016/j.tcs.2010.10.023412:24(2577-2587)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.tcs.2010.10.023
Azar YMądry AMoscibroda TPanigrahi DSrinivasan AMatias Y(2009)Maximum Bipartite Flow in Networks with Adaptive Channel WidthProceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming: Part II10.1007/978-3-642-02930-1_29(351-362)Online publication date: 3-Jul-2009
https://dl.acm.org/doi/10.1007/978-3-642-02930-1_29
Goldberg A(2006)Recent developments in maximum flow algorithmsAlgorithm Theory — SWAT'9810.1007/BFb0054350(1-10)Online publication date: 26-May-2006
https://doi.org/10.1007/BFb0054350
Nagamochi H(2005)On computing minimum (s,t)-cuts in digraphsInformation Processing Letters10.1016/j.ipl.2004.11.00693:5(231-237)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1016/j.ipl.2004.11.006
Karger DLevine MReif J(2002)Random sampling in residual graphsProceedings of the thiry-fourth annual ACM symposium on Theory of computing10.1145/509907.509918(63-66)Online publication date: 19-May-2002
https://dl.acm.org/doi/10.1145/509907.509918
Asano TAsano Y(2000)RECENT DEVELOPMENTS IN MAXIMUM FLOW ALGORITHMSJournal of the Operations Research Society of Japan10.15807/jorsj.43.243:1(2-31)Online publication date: 2000
https://doi.org/10.15807/jorsj.43.2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On flows in bidirected graphs

Nowhere-zero 3-flows in triangularly connected graphs

Nowhere-Zero Flows in Random Graphs