{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:12:30Z","timestamp":1757311950143,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            We present the first\n            <jats:italic>near-linear work<\/jats:italic>\n            and\n            <jats:italic>poly-logarithmic depth<\/jats:italic>\n            algorithm for computing a\n            <jats:italic>minimum cut<\/jats:italic>\n            in an undirected graph. Previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices.\n          <\/jats:p>\n          <jats:p>\n            In a graph with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges, our randomized algorithm computes the minimum cut with high probability in\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 and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) depth. This result is obtained by parallelizing a data structure that aggregates weights along paths in a tree, in addition exploiting the connection between minimum cuts and approximate maximum packings of spanning trees.\n          <\/jats:p>\n          <jats:p>In addition, our algorithm improves upon bounds on the number of cache misses incurred to compute a minimum cut.<\/jats:p>","DOI":"10.1145\/3460890","type":"journal-article","created":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T10:47:26Z","timestamp":1629715646000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallel Minimum Cuts in Near-linear Work and Low Depth"],"prefix":"10.1145","volume":"8","author":[{"given":"Barbara","family":"Geissmann","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lukas","family":"Gianinazzi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,8,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759076"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/160688.160704"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_2_1_7_1","first-page":"1277","article-title":"Algorithm\u00a0for solution of a problem of maximum flow in a network with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","unstructured":"E. A. Dinic . 1970 . Algorithm\u00a0for solution of a problem of maximum flow in a network with power estimation . Sov. Math Dokl. 11 , 5 (1970), 1277 \u2013 1280 . E. A. Dinic. 1970. Algorithm\u00a0for solution of a problem of maximum flow in a network with power estimation. Sov. Math Dokl. 11, 5 (1970), 1277\u20131280.","journal-title":"Sov. Math Dokl."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_9_1","unstructured":"Pawe\u0142 Gawrychowski Shay Mozes and Oren Weimann. 2019. Minimum cut in O(m log2 n) time. arXiv:1911.01145. Retrieved from https:\/\/arxiv.org\/abs\/1911.01145.  Pawe\u0142 Gawrychowski Shay Mozes and Oren Weimann. 2019. Minimum cut in O(m log2 n) time. arXiv:1911.01145. Retrieved from https:\/\/arxiv.org\/abs\/1911.01145."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_24"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400259"},{"key":"e_1_2_1_12_1","unstructured":"Lukas Gianinazzi and Torsten Hoefler. 2020. Parallel planar subgraph isomorphism and vertex connectivity. arXiv:2007.01199. Retrieved from https:\/\/arxiv.org\/abs\/2007.01199.  Lukas Gianinazzi and Torsten Hoefler. 2020. Parallel planar subgraph isomorphism and vertex connectivity. arXiv:2007.01199. Retrieved from https:\/\/arxiv.org\/abs\/2007.01199."},{"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":"publisher","DOI":"10.1006\/jagm.1994.1043"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00142-3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1180335"},{"key":"e_1_2_1_17_1","unstructured":"Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann.  Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298340"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501387141"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_2_1_22_1","volume-title":"Karp and Vijaya Ramachandran","author":"Richard","year":"1990","unstructured":"Richard M. Karp and Vijaya Ramachandran . 1990 . Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science , Volume A: Algorithms and Complexity (A). 869\u2013 942 . Richard M. Karp and Vijaya Ramachandran. 1990. Parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A). 869\u2013942."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746588"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.43"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52921-7_51"},{"key":"e_1_2_1_27_1","volume-title":"Papadimitriou and Kenneth Steiglitz","author":"Christos","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz . 1998 . Combinatorial Optimization : Algorithms and Complexity. Courier Corporation , 117\u2013120 pages. Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, 117\u2013120 pages."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0820"},{"key":"e_1_2_1_31_1","volume-title":"Synthesis of Parallel Algorithms","author":"Reif John H.","unstructured":"John H. Reif . 1993. Synthesis of Parallel Algorithms ( 1 st ed.). Morgan Kaufmann, San Francisco , CA. John H. Reif. 1993. Synthesis of Parallel Algorithms (1st ed.). Morgan Kaufmann, San Francisco, CA.","edition":"1"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB\u201900)","author":"Sharan Roded","year":"2000","unstructured":"Roded Sharan and Ron Shamir . 2000 . Center CLICK: A clustering algorithm with applications to gene expression analysis . In Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB\u201900) . 307\u2013316. Roded Sharan and Ron Shamir. 2000. Center CLICK: A clustering algorithm with applications to gene expression analysis. In Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB\u201900). 307\u2013316."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:29Z","timestamp":1750195469000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3460890"],"URL":"https:\/\/doi.org\/10.1145\/3460890","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}