{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:27:29Z","timestamp":1673987249389},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,1]]},"abstract":"\n We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a \"semiduality\" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an\n m<\/jats:italic>\n -edge,\n n<\/jats:italic>\n -vertex graph with high probability in\n O<\/jats:italic>\n (m log\n 3<\/jats:sup>\n n<\/jats:italic>\n ) time. We also give a simpler randomized algorithm that finds\n all<\/jats:italic>\n minimum cuts with high probability in O(\n m<\/jats:italic>\n log\n 3<\/jats:sup>\n n<\/jats:italic>\n ) time. This variant has an optimal\n RNC<\/jats:italic>\n parallelization. Both variants improve on the previous best time bound of\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 2<\/jats:sup>\n log\n 3<\/jats:sup>\n n<\/jats:italic>\n ). Other applications of the tree-packing approach are new, nearly tight bounds on the number of\n near-minimum<\/jats:italic>\n cuts a graph may have and a new data structure for representing them in a space-efficient manner.\n <\/jats:p>","DOI":"10.1145\/331605.331608","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"46-76","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":128,"title":["Minimum cuts in near-linear time"],"prefix":"10.1145","volume":"47","author":[{"given":"David R.","family":"Karger","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]}],"member":"320","published-online":{"date-parts":[[2000,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.1.104"},{"key":"e_1_2_1_2_1","first-page":"92","volume-title":"Proceedings of the 36th Annual Symposium on the Foundations of Computer Science, (Oct.). IEEE Computer Society Press, Los Alamitos, Calif.","author":"BENCZUR A. A.","year":"1995"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"e_1_2_1_4_1","unstructured":"BOLLOBAS B. 1985. Random Graphs. Harcourt Brace Janovich San Diego Calif. BOLLOBAS B. 1985. Random Graphs. Harcourt Brace Janovich San Diego Calif."},{"key":"e_1_2_1_5_1","first-page":"116","volume-title":"Proceedings of the 16th Annual International A CM SIGIR Conference on Research and Development in Information Retrieval","author":"BOTAFOGO R.A.","year":"1993"},{"key":"e_1_2_1_6_1","first-page":"393","article-title":"Solution of a large-scale traveling salesman problem","volume":"2","author":"DANTZIG G. B.","year":"1954","journal-title":"Oper. Re."},{"key":"e_1_2_1_7_1","first-page":"290","volume-title":"Studies in Discrete Optimization","author":"DINITZ E. A."},{"key":"e_1_2_1_8_1","first-page":"91","volume-title":"Algorithmics Press","author":"EDMONDS J.","year":"1972"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1022"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","article-title":"A linear time algorithm for a special case of disjoint set union","volume":"30","author":"GABOW H. N.","year":"1985","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF01758774","article-title":"Forests, frames, and games: Algorithms for matroid sums and applications","volume":"7","author":"GABOW H. N.","year":"1992","journal-title":"Algorithmica"},{"key":"e_1_2_1_12_1","unstructured":"GAREY M. R. AND JOHNSON D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company San Francisco Calif. GAREY M. R. AND JOHNSON D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company San Francisco Calif."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"GOMORY R. E.","year":"1961","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00079-8"},{"key":"e_1_2_1_18_1","first-page":"79","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing, (Dallas, Tex., May 23-26)","author":"HOLM J.","year":"1998"},{"key":"e_1_2_1_19_1","first-page":"363","volume-title":"Proceedings of the 4th Annual A CM Symposium on Parallel Algorithms and Architectures","author":"JOHNSON D. B.","year":"1992"},{"key":"e_1_2_1_20_1","first-page":"21","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"KARGER D. R.","year":"1993"},{"key":"e_1_2_1_21_1","unstructured":"KARGER D. R. 1994. Random Sampling in Graph Optimization Problems. Ph.D. dissertation. Stanford University Stanford Calif. Contact at karger@ics mit. edu. Available from http :\/\/ theory.lcs.mit.edu\/~karger. KARGER D. R. 1994. Random Sampling in Graph Optimization Problems. Ph.D. dissertation. Stanford University Stanford Calif. Contact at karger@ics mit. edu. Available from http :\/\/ theory.lcs.mit.edu\/~karger."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01585865","article-title":"Random sampling and greedy sparsification in matroid optimization problems","volume":"82","author":"KARGER D.R.","year":"1998","journal-title":"Math. Prog. B"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298340"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_26_1","first-page":"869","volume-title":"Mass.","author":"KARP R. M.","year":"1990"},{"key":"e_1_2_1_27_1","unstructured":"LAWLER E. L. LENSTRA J. K. RINOOY NAN A. H. G. AND SHMOYS D. B. EDS. 1985. The Traveling Salesman Problem. Wiley New York. LAWLER E. L. LENSTRA J. K. RINOOY NAN A. H. G. AND SHMOYS D. B. EDS. 1985. The Traveling Salesman Problem. Wiley New York."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"MOTWANI R. AND RAGHAVAN P. 1995. Randomized Algorithms. Cambridge University Press New York N. Y. MOTWANI R. AND RAGHAVAN P. 1995. Randomized Algorithms. Cambridge University Press New York N. Y.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01758778","article-title":"Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs","volume":"7","author":"NAGAMOCHI H.","year":"1992","journal-title":"Algorithmica"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","article-title":"Edge disjoint spanning trees of finite graphs","volume":"36","author":"NASH-WILLIAMS C.","year":"1961","journal-title":"J. London Math. Soc."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"},{"key":"e_1_2_1_34_1","first-page":"394","article-title":"Selected applications of minimum cuts in networks","author":"PICARD J.-C.","year":"1982","journal-title":"LN.F.O.R: Canad. J. Oper. Res. Inf. Proc. 20"},{"key":"e_1_2_1_35_1","first-page":"495","volume-title":"Proceedings of the 32nd Annual Symposium on the Foundations of Computer Science. (Oct.) IEEE Computer Society Press, Los Alamitos, Calif.","author":"PLOTKIN S.","year":"1991"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_38_1","series-title":"Lecture Notes in Computer Science","first-page":"366","volume-title":"Automata, Languages and Programming. 19th International Colloquium Proceedings","author":"VAZIRANI V. V."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/331605.331608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T06:27:52Z","timestamp":1672554472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/331605.331608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1145\/331605.331608"],"URL":"http:\/\/dx.doi.org\/10.1145\/331605.331608","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,1]]},"assertion":[{"value":"2000-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}