{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T20:10:40Z","timestamp":1771877440941,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["No. CCF-1901381, No. CCF-1910030, No. CCF-1919223"],"award-info":[{"award-number":["No. CCF-1901381, No. CCF-1910030, No. CCF-1919223"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            We present a randomized\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) work,\n            <jats:italic>O<\/jats:italic>\n            (polylog\n            <jats:italic>n<\/jats:italic>\n            ) depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP\u201920], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA\u201918], which performs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:sup>4<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) work in\n            <jats:italic>O<\/jats:italic>\n            (polylog\n            <jats:italic>n<\/jats:italic>\n            ) depth.\n          <\/jats:p>\n          <jats:p>Our algorithm makes use of three components that might be of independent interest. First, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Second, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger\u2019s sequential algorithm for minimum cuts. Last, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem.<\/jats:p>","DOI":"10.1145\/3565557","type":"journal-article","created":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T13:22:27Z","timestamp":1671196947000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Parallel Minimum Cuts in\n            <i>O<\/i>\n            (\n            <i>m<\/i>\n            log\n            <sup>2<\/sup>\n            <i>n<\/i>\n            ) Work and Low Depth"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5853-0472","authenticated-orcid":false,"given":"Daniel","family":"Anderson","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0224-9187","authenticated-orcid":false,"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201920)","author":"Acar Umut A.","year":"2020","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel batch-dynamic trees via change propagation. In Proceedings of the European Symposium on Algorithms (ESA\u201920)."},{"key":"e_1_3_1_3_2","volume-title":"Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX\u201905)","author":"Acar Umut A.","year":"2005","unstructured":"Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. 2005. An experimental analysis of change propagation in dynamic trees. In Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX\u201905)."},{"issue":"2","key":"e_1_3_1_4_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1103963.1103966","article-title":"Maintaining information in fully dynamic trees with top trees","volume":"1","author":"Alstrup Stephen","year":"2005","unstructured":"Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. 2005. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1, 2 (2005), 243\u2013264.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_1_5_2","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201920)","author":"Anderson Daniel","year":"2020","unstructured":"Daniel Anderson, Guy E. Blelloch, and Kanat Tangwongsan. 2020. Work-efficient batch-incremental minimum spanning trees with applications to the sliding window model. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201920)."},{"issue":"3","key":"e_1_3_1_6_2","article-title":"Programming parallel algorithms","volume":"39","author":"Blelloch Guy E.","year":"1996","unstructured":"Guy E. Blelloch. 1996. Programming parallel algorithms. Commun. ACM 39, 3 (Mar.1996).","journal-title":"Commun. ACM"},{"key":"e_1_3_1_7_2","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201920)","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal parallel algorithms in the binary-forking model. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201920)."},{"issue":"1","key":"e_1_3_1_8_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1137\/0222013","article-title":"Scan-first search and sparse certificates: An improved parallel algorithm for k-vertex connectivity","volume":"22","author":"Cheriyan Joseph","year":"1993","unstructured":"Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna Thurimella. 1993. Scan-first search and sparse certificates: An improved parallel algorithm for k-vertex connectivity. SIAM J. Comput. 22, 1 (1993), 157\u2013174.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_1_9_2","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201996)","author":"Cole Richard","year":"1996","unstructured":"Richard Cole, Philip N. Klein, and Robert E. Tarjan. 1996. Finding minimum spanning forests in logarithmic time and linear work using random sampling. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201996)."},{"issue":"4","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00453-015-0077-8","article-title":"Exact sublinear binomial sampling","volume":"73","author":"Farach-Colton Mart\u00edn","year":"2015","unstructured":"Mart\u00edn Farach-Colton and Meng-Tsung Tsai. 2015. Exact sublinear binomial sampling. Algorithmica 73, 4 (2015), 637\u2013651.","journal-title":"Algorithmica"},{"issue":"2","key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1006\/jcss.1995.1022","article-title":"A matroid approach to finding edge connectivity and packing arborescences","volume":"50","author":"Gabow Harold N.","year":"1995","unstructured":"Harold N. Gabow. 1995. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. 50, 2 (1995), 259\u2013273.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_1_12_2","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201920)","author":"Gawrychowski Pawe\u0142","year":"2020","unstructured":"Pawe\u0142 Gawrychowski, Shay Mozes, and Oren Weimann. 2020. Minimum cut in \\({O}(m\\log ^{2} n)\\) time. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP\u201920)."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-1-4684-5511-3_9","volume-title":"Concurrent Computations","author":"Gazit H.","year":"1988","unstructured":"H. Gazit, Gary L. Miller, and ShangHua Teng. 1988. Optimal tree contraction in the EREW model. In Concurrent Computations. Plenum Press, 139\u2013156."},{"key":"e_1_3_1_14_2","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201918)","author":"Geissmann Barbara","year":"2018","unstructured":"Barbara Geissmann and Lukas Gianinazzi. 2018. Parallel minimum cuts in near-linear work and low depth. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201918)."},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari and Fabian Kuhn. 2013. Distributed minimum cut approximation. In Proceedings of the International Symposium on Distributed Computing (DISC\u201913) .","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_1_16_2","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Ghaffari Mohsen","year":"2020","unstructured":"Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. 2020. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)."},{"issue":"4","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory Ralph E.","year":"1961","unstructured":"Ralph E. Gomory and Tien Chung Hu. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9, 4 (1961), 551\u2013570.","journal-title":"J. Soc. Indust. Appl. Math."},{"issue":"3","key":"e_1_3_1_18_2","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1006\/jagm.1994.1043","article-title":"A faster algorithm for finding the minimum cut in a directed graph","volume":"17","author":"Hao J. X.","year":"1994","unstructured":"J. X. Hao and James B. Orlin. 1994. A faster algorithm for finding the minimum cut in a directed graph. J. Algor. 17, 3 (1994), 424\u2013446.","journal-title":"J. Algor."},{"issue":"2","key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast algorithms for finding nearest common ancestors","volume":"13","author":"Harel Dov","year":"1984","unstructured":"Dov Harel and Robert Endre Tarjan. 1984. Fast algorithms for finding nearest common ancestors. SIAM J. Computing 13, 2 (1984), 338\u2013355.","journal-title":"SIAM J. Computing"},{"key":"e_1_3_1_20_2","unstructured":"Lorenz H\u00fcbschle-Schneider and Peter Sanders. 2019. Parallel weighted random sampling. Retrieved from https:\/\/arXiv:1903.00227."},{"key":"e_1_3_1_21_2","volume-title":"Random Sampling in Graph Optimization Problems","author":"Karger David","year":"1995","unstructured":"David Karger. 1995. Random Sampling in Graph Optimization Problems. Ph.D. Dissertation. Stanford University."},{"key":"e_1_3_1_22_2","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993)","author":"Karger David R.","year":"1993","unstructured":"David R. Karger. 1993. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993)."},{"issue":"2","key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1287\/moor.24.2.383","article-title":"Random sampling in cut, flow, and network design problems","volume":"24","author":"Karger David R.","year":"1999","unstructured":"David R. Karger. 1999. Random sampling in cut, flow, and network design problems. Math. Oper. Res. 24, 2 (1999), 383\u2013413.","journal-title":"Math. Oper. Res."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"issue":"2","key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/201019.201022","article-title":"A randomized linear-time algorithm to find minimum spanning trees","volume":"42","author":"Karger David R.","year":"1995","unstructured":"David R. Karger, Philip N. Klein, and Robert E. Tarjan. 1995. A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 2 (1995), 321\u2013328.","journal-title":"J. ACM"},{"key":"e_1_3_1_26_2","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC)","author":"Karger David R.","year":"1994","unstructured":"David R. Karger and Rajeev Motwani. 1994. Derandomization through approximation: An NC algorithm for minimum cuts. In Proceedings of the ACM Symposium on Theory of Computing (STOC)."},{"issue":"4","key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","article-title":"A new approach to the minimum cut problem","volume":"43","author":"Karger David R.","year":"1996","unstructured":"David R. Karger and Clifford Stein. 1996. A new approach to the minimum cut problem. J. ACM 43, 4 (1996), 601\u2013640.","journal-title":"J. ACM"},{"key":"e_1_3_1_28_2","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201921)","author":"Li Jason","year":"2021","unstructured":"Jason Li. 2021. Deterministic mincut in almost-linear time. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201921)."},{"key":"e_1_3_1_29_2","volume-title":"Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT\u201920)","author":"Lovett Antonio Molina","year":"2020","unstructured":"Antonio Molina Lovett and Bryce Sandlund. 2020. A simple algorithm for minimum cuts in near-linear time. In Proceedings of the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT\u201920)."},{"key":"e_1_3_1_30_2","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993)","author":"Matula David W.","year":"1993","unstructured":"David W. Matula. 1993. A linear time 2+ \\(\\varepsilon\\) approximation algorithm for edge connectivity. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201993)."},{"key":"e_1_3_1_31_2","first-page":"47","volume-title":"Randomness and Computation","author":"Miller Gary L.","year":"1989","unstructured":"Gary L. Miller and John H. Reif. 1989. Parallel tree contraction part 1: Fundamentals. In Randomness and Computation, Vol. 5. 47\u201372."},{"issue":"1","key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1137\/0405004","article-title":"Computing edge-connectivity in multigraphs and capacitated graphs","volume":"5","author":"Nagamochi Hiroshi","year":"1992","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki. 1992. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5, 1 (1992), 54\u201366.","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01758778","article-title":"A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph","volume":"7","author":"Nagamochi Hiroshi","year":"1992","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki. 1992. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 1-6 (1992), 583\u2013596.","journal-title":"Algorithmica"},{"issue":"1","key":"e_1_3_1_34_2","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":"1","author":"Nash-Williams C. St. J. A.","year":"1961","unstructured":"C. St. J. A. Nash-Williams. 1961. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 1, 1 (1961), 445\u2013450.","journal-title":"J. London Math. Soc."},{"issue":"2","key":"e_1_3_1_35_2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","article-title":"Fast approximation algorithms for fractional packing and covering problems","volume":"20","author":"Plotkin Serge A.","year":"1995","unstructured":"Serge A. Plotkin, David B. Shmoys, and \u00c9va Tardos. 1995. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20, 2 (1995), 257\u2013301.","journal-title":"Math. Oper. Res."},{"issue":"3","key":"e_1_3_1_36_2","article-title":"Optimal and sublogarithmic time randomized parallel sorting algorithms","volume":"18","author":"Rajasekaran Sanguthevar","year":"1989","unstructured":"Sanguthevar Rajasekaran and John H. Reif. 1989. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. Computing 18, 3 (1989).","journal-title":"SIAM J. Computing"},{"issue":"6","key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1137\/0217079","article-title":"On finding lowest common ancestors: Simplification and parallelization","volume":"17","author":"Schieber Baruch","year":"1988","unstructured":"Baruch Schieber and Uzi Vishkin. 1988. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput. 17, 6 (1988), 1253\u20131262.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A data structure for dynamic trees","volume":"26","author":"Sleator Daniel D.","year":"1983","unstructured":"Daniel D. Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3 (1983), 362\u2013391.","journal-title":"J. Comput. Syst. Sci."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565557","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3565557","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:51Z","timestamp":1750182531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565557"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3565557"],"URL":"https:\/\/doi.org\/10.1145\/3565557","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,14]]},"assertion":[{"value":"2021-12-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}