{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T11:15:15Z","timestamp":1762254915136,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T00:00:00Z","timestamp":1718150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["592\/17","592\/17"],"award-info":[{"award-number":["592\/17","592\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give a randomized algorithm that finds a minimum cut in an undirected weighted <jats:italic>m<\/jats:italic>-edge <jats:italic>n<\/jats:italic>-vertex graph <jats:italic>G<\/jats:italic> with high probability in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(m \\log ^2 n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. This is the first improvement to Karger\u2019s celebrated <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(m \\log ^3 n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm from 1996. Our main technical contribution is a deterministic <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(m \\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithm that, given a spanning tree <jats:italic>T<\/jats:italic> of <jats:italic>G<\/jats:italic>, finds a minimum cut of <jats:italic>G<\/jats:italic> that 2-respects (cuts two edges of) <jats:italic>T<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00224-024-10179-7","type":"journal-article","created":{"date-parts":[[2024,6,12]],"date-time":"2024-06-12T06:01:40Z","timestamp":1718172100000},"page":"814-834","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Minimum Cut in $$O(m\\log ^2 n)$$ Time"],"prefix":"10.1007","volume":"68","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":false,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,12]]},"reference":[{"key":"10179_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Krauthgamer, R., Li, J., Panigrahi, D., Saranurak, T., Trabelsi, O.: Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In 63rd FOCS, pp. 884\u2013895 (2022)","DOI":"10.1109\/FOCS54457.2022.00088"},{"issue":"2","key":"10179_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., Lichtenberg, K.D., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"10179_CR3","unstructured":"Bhardwaj, N., Lovett, A.M., Sandlund, B.: A simple algorithm for minimum cuts in near-linear time. In 17th SWAT, vol. 162, pp. 12(18), 1\u201312 (2020)"},{"key":"10179_CR4","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Pedersen, C.N.S.: Computing the quartet distance between evolutionary trees in time $${O}(n \\log ^2 n)$$. In 12th ISAAC, pp. 731\u2013742 (2001)","DOI":"10.1007\/3-540-45678-3_62"},{"key":"10179_CR5","doi-asserted-by":"crossref","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Maximum flow and minimum-cost flow in almost-linear time. In 63rd FOCS, pp. 612\u2013623 (2022)","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"10179_CR6","volume-title":"Flows netw.","author":"LR Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows netw. Princeton Univ, Press (1962)"},{"key":"10179_CR7","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2), 259\u2013273 (1995) Announced at STOC 1991","DOI":"10.1006\/jcss.1995.1022"},{"key":"10179_CR8","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In 16th STOC, pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"10179_CR9","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Mozes, S., Weimann, O.: A note on a recent algorithm for minimum cut. In 4th SOSA, pp. 74\u201379 (2021)","DOI":"10.1137\/1.9781611976496.8"},{"key":"10179_CR10","doi-asserted-by":"crossref","unstructured":"Geissmann B., Gianinazzi, L.: Parallel minimum cuts in near-linear work and low depth. In 30th SPAA, pp. 1\u201311 (2018)","DOI":"10.1145\/3210377.3210393"},{"key":"10179_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K., Thorup, M.: Faster algorithms for edge connectivity via random 2-out contractions. CoRR, abs\/1909.00844 (2019)","DOI":"10.1137\/1.9781611975994.77"},{"issue":"5","key":"10179_CR12","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"AV Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM. 45(5), 783\u2013797 (1998)","journal-title":"J. ACM."},{"issue":"4","key":"10179_CR13","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM. 35(4), 921\u2013940 (1988)","journal-title":"J. ACM."},{"key":"10179_CR14","doi-asserted-by":"crossref","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","DOI":"10.1137\/0109047"},{"issue":"3","key":"10179_CR15","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J Hao","year":"1994","unstructured":"Hao, J., Orlin, J.B.: A faster algorithm for finding the minimum cut in a directed graph. J. Algorithm. 17(3), 424\u2013446 (1994)","journal-title":"J. Algorithm."},{"issue":"2","key":"10179_CR16","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM. J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM. J. Comput."},{"key":"10179_CR17","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Li, J., Rao, S., Wang, D.: Deterministic near-linear time minimum cut in weighted graphs. In 28th SODA, page To appear, (2024)","DOI":"10.1137\/1.9781611977912.111"},{"key":"10179_CR18","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Rao, S., Wang, D.: Local flow partitioning for faster edge connectivity. In 28th SODA, pp. 1919\u20131938 (2017)","DOI":"10.1137\/1.9781611974782.125"},{"key":"10179_CR19","unstructured":"Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In 4th SODA, pp. 21\u201330 (1993)"},{"key":"10179_CR20","unstructured":"Karger, D.R.: Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, Stanford, CA 94305, (1994)"},{"key":"10179_CR21","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2), 383\u2013413 (1999) Announced at STOC 1994","DOI":"10.1287\/moor.24.2.383"},{"issue":"2","key":"10179_CR22","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1287\/moor.24.2.383","volume":"24","author":"DR Karger","year":"1999","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. Math. Oper. Res. 24(2), 383\u2013413 (1999)","journal-title":"Math. Oper. Res."},{"key":"10179_CR23","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM, 47(1), 46\u201376 (2000) Announced at STOC 1996","DOI":"10.1145\/331605.331608"},{"issue":"2","key":"10179_CR24","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"DR Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM. 42(2), 321\u2013328 (1995)","journal-title":"J. ACM."},{"issue":"4","key":"10179_CR25","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"DR Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM. 43(4), 601\u2013640 (1996)","journal-title":"J. ACM."},{"key":"10179_CR26","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Thorup, M.: Deterministic edge connectivity in near-linear time. J. ACM, 66(1), 4 1\u201350 (2019)","DOI":"10.1145\/3274663"},{"key":"10179_CR27","doi-asserted-by":"crossref","unstructured":"King, V., Rao, S., Tarjan, R.E.: A faster deterministic maximum flow algorithm. J. Algorithms, 17(3), 447\u2013474 (1994) Announced at SODA 1992","DOI":"10.1006\/jagm.1994.1044"},{"key":"10179_CR28","unstructured":"Klein P.N., Mozes, S.: Optimization algorithms for planar graphs. http:\/\/planarity.org. Book draft"},{"issue":"4","key":"10179_CR29","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1080\/00031305.1979.10482697","volume":"33","author":"RA Kronmal","year":"1979","unstructured":"Kronmal, R.A., Peterson, A.V.: On the alias method for generating random variables from a discrete distribution. Am. Stat. 33(4), 214\u2013218 (1979)","journal-title":"Am. Stat."},{"key":"10179_CR30","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A.: Path finding methods for linear programming: Solving linear programs in $$\\tilde{O}(\\sqrt{rank})$$ iterations and faster algorithms for maximum flow. In 55th FOCS, pp. 424\u2013433 (2014)","DOI":"10.1109\/FOCS.2014.52"},{"key":"10179_CR31","doi-asserted-by":"crossref","unstructured":"Madry, A.: Computing maximum flow with augmenting electrical flows. In 57th FOCS, pp. 593\u2013602 (2016)","DOI":"10.1109\/FOCS.2016.70"},{"key":"10179_CR32","unstructured":"Matula, D.W.: A linear time $$2+\\epsilon $$ approximation algorithm for edge connectivity. In 4th SODA, pp. 500\u2013504 (1993)"},{"key":"10179_CR33","doi-asserted-by":"crossref","unstructured":"Mukhopadhyay, S., Nanongkai, D.: Weighted min-cut: sequential, cut-query, and streaming algorithms. In 52nd STOC, pp. 496\u2013509 (2020)","DOI":"10.1145\/3357713.3384334"},{"issue":"1","key":"10179_CR34","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discret. Math. 5(1), 54\u201366 (1992)","journal-title":"SIAM J. Discret. Math."},{"issue":"5 &6","key":"10179_CR35","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse $$k$$-connected spanning subgraph of a $$k$$-connected graph. Algorithmica 7(5 &6), 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"10179_CR36","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge disjoint spanning trees of finite graphs. J Lond Math Soc 36, 445\u2013450 (1961)","journal-title":"J Lond Math Soc"},{"key":"10179_CR37","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $${O}(nm)$$ time, or better. In 45th STOC, pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"issue":"2","key":"10179_CR38","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"10179_CR39","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"10179_CR40","doi-asserted-by":"crossref","unstructured":"Thorup, M., Karger, D.R.: Dynamic graph algorithms with applications. In 7th SWAT, pp. 1\u20139 (2000)","DOI":"10.1007\/3-540-44985-X_1"},{"key":"10179_CR41","doi-asserted-by":"crossref","unstructured":"van\u00a0den Brand, J., Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sushant\u00a0Sachdeva, A.S.: A deterministic almost-linear time algorithm for minimum-cost flow. In 64rd FOCS, (2023) To appear","DOI":"10.1109\/FOCS57990.2023.00037"},{"issue":"4","key":"10179_CR42","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM. 23(4), 229\u2013239 (1980)","journal-title":"Commun. ACM."},{"issue":"1","key":"10179_CR43","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1049\/el:19740097","volume":"10","author":"A Walker","year":"1974","unstructured":"Walker, A.: New fast method for generating discrete random numbers with arbitrary frequency distributions. Electronics Letters 10(1), 127\u2013128 (April 1974)","journal-title":"Electronics Letters"},{"key":"10179_CR44","unstructured":"Young, N.E.: Randomized rounding without solving the linear program. In 6th SODA, pp. 170\u2013178 (1995)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10179-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10179-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10179-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:18:35Z","timestamp":1724447915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10179-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,12]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10179"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10179-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,6,12]]},"assertion":[{"value":"13 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}