The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
A new approach to the minimum cut problem
Open accessAbstract
This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n 2 log 3 n) time, a significant improvement over the previous O˜(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with n 2 processors; this gives the first proof that the minimum cut problem can be solved in RNC . The algorithm does more than find a single minimum cut; it finds all of them. With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of α of the minimum cut's in expected O˜(n 2α ) time, or in RNC with n 2α processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected O˜(n 2(r-1) ) time, or in RNC with n 2(r-1) processors. The “trace” of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,072
A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
Chernoff, H. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729330 · Cited by 3,550
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Edmonds, J., & Karp, R. M. (1972) · Journal of the ACM · doi:10.1145/321694.321699 · Cited by 2,528
Maximal Flow Through a Network
Ford, L. R., & Fulkerson, D. R. (1956) · Canadian Journal of Mathematics · doi:10.4153/cjm-1956-045-5 · Cited by 2,410
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
Maximal Flow Through a Network
Ford, L. R., & Fulkerson, D. R. (2009) · Classic Papers in Combinatorics · doi:10.1007/978-0-8176-4842-8_15 · Cited by 1,829
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
The Traveling Salesman Problem
(2019) · Fundamentals of Supply Chain Theory · doi:10.1002/9781119584445.ch10 · Cited by 1,614
Solution of a Large-Scale Traveling-Salesman Problem
Dantzig, G. B., Fulkerson, R., & Johnson, S. M. (1954) · Journal of the Operations Research Society of America · doi:10.1287/opre.2.4.393 · Cited by 1,483
Solution of a Large-Scale Traveling-Salesman Problem
Chvátal, V., Cook, W. J., Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_1 · Cited by 1,263
A data structure for dynamic trees
Sleator, D. D., & Tarjan, R. E. (1983) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(83)90006-5 · Cited by 1,018
CBMS-NSF REGIONAL CONFERENCE SERIES IN APPLIED MATHEMATICS
Gottlieb, D., Orszag, S. A., Huber, P. J., & Roberts, F. S. (2011) · Cited by 999
Parallel Algorithms for Shared-Memory Machines
Karp, R. M., & Ramachandran, V. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50022-9 · Cited by 687
An O(logn) parallel connectivity algorithm
Shiloach, Y., & Vishkin, U. (1982) · Journal of Algorithms · doi:10.1016/0196-6774(82)90008-6 · Cited by 672
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
Almost optimal lower bounds for small depth circuits
Hastad, J. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12132 · Cited by 620
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.383347 · Cited by 609
A note on the maximum flow through a network
Elias, P., Feinstein, A., & Shannon, C. (1956) · IEEE Transactions on Information Theory · doi:10.1109/tit.1956.1056816 · Cited by 456
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · Combinatorica · doi:10.1007/bf02579206 · Cited by 388
THE COMPLEXITY OF NONUNIFORM RANDOM NUMBER GENERATION.
Knuth, D. E., & Yao, A. C.-C. (1976) · Cited by 256
Minimum cuts and related problems
Picard, J. C., & Ratliff, H. D. (1975) · Networks · doi:10.1002/net.3230050405 · Cited by 245
Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm
Karger, D. R. (1993) · doi:10.5555/313559.313605 · Cited by 238
Self-citationThe complexity of multiway cuts (extended abstract)
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129736 · Cited by 221
The maximum flow problem is log space complete for P
Goldschlager, L. M., Shaw, R. A., & Staples, J. (1982) · Theoretical Computer Science · doi:10.1016/0304-3975(82)90092-5 · Cited by 145
Cluster analysis for hypertext systems
Botafogo, R. A. (1993) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/160688.160704 · Cited by 99
Croft, W. B., & van Rijsbergen, C. J. (1994) · Cited by 59
Cited by
Frieze, A., & Karoński, M. (2015) · doi:10.1017/cbo9781316339831 · Cited by 576
Metadata
- Authors
- Karger, D. R., & Stein, C.
- Venue
- Journal of the ACM
- Published
- 1996-07
- Volume
- 43
- Issue
- 4
- Pages
- 601-640
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2168919539
- Cited by
- 485
- References
- 30
- FWCI
- 13.91
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.