{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:18:41Z","timestamp":1757312321718,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["853109"],"award-info":[{"award-number":["853109"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Polish National Science Centre","award":["019\/32\/T\/ST6\/00566"],"award-info":[{"award-number":["019\/32\/T\/ST6\/00566"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,31]]},"DOI":"10.1145\/3382734.3405737","type":"proceedings-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T22:33:55Z","timestamp":1596234835000},"page":"119-128","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Massively Parallel Algorithms for Minimum Cut"],"prefix":"10.1145","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"ETH Zurich"}]},{"given":"Krzysztof","family":"Nowicki","sequence":"additional","affiliation":[{"name":"University of Wroclaw"}]}],"member":"320","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1616","volume-title":"Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Pro. of Symp. on Disc. Alg. (SODA)","author":"Assadi Sepehr","year":"2019","unstructured":"[ABB+19] Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab S. Mirrokni , and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Pro. of Symp. on Disc. Alg. (SODA) , pages 1616 -- 1635 , 2019 . [ABB+19] Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Pro. of Symp. on Disc. Alg. (SODA), pages 1616--1635, 2019."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755586"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_5_1","volume-title":"Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599","author":"Assadi Sepehr","year":"2017","unstructured":"[Ass17] Sepehr Assadi . Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599 , 2017 . [Ass17] Sepehr Assadi. Simple round compression for parallel vertex cover. arXiv preprint arXiv:1709.04599, 2017."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00070"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_8_1","first-page":"1","volume-title":"Lang. and Prog. (ICALP)","volume":"132","author":"Andoni Alexandr","year":"2019","unstructured":"[ASZ19] Alexandr Andoni , Clifford Stein , and Peilin Zhong . Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In Pro. of the Int'l Colloq. on Automata , Lang. and Prog. (ICALP) , volume 132 , pages 14: 1 -- 14 :16, 2019 . [ASZ19] Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In Pro. of the Int'l Colloq. on Automata, Lang. and Prog. (ICALP), volume 132, pages 14:1--14:16, 2019."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331609"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00095"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.76"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24922-9_9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00096"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465224"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188764"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210393"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331603"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_24_1","first-page":"2201","volume-title":"Proc. of Conf. on Machine Learning (ICML)","volume":"97","author":"Ghaffari Mohsen","year":"2019","unstructured":"[GLM19] Mohsen Ghaffari , Silvio Lattanzi , and Slobodan Mitrovic . Improved parallel algorithms for density-based network clustering . In Proc. of Conf. on Machine Learning (ICML) , volume 97 , pages 2201 -- 2210 , 2019 . [GLM19] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic. Improved parallel algorithms for density-based network clustering. In Proc. of Conf. on Machine Learning (ICML), volume 97, pages 2201--2210, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_1_26_1","first-page":"374","volume-title":"ISAAC'11","author":"Goodrich Michael T.","year":"2011","unstructured":"[GSZ11] Michael T. Goodrich , Nodari Sitchinava , and Qin Zhang . Sorting, searching , and simulation in the mapreduce framework . In ISAAC'11 , pages 374 -- 383 . Springer-Verlag , 2011 . [GSZ11] Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In ISAAC'11, pages 374--383. Springer-Verlag, 2011."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.99"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.029"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323202"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_33_1","first-page":"21","volume-title":"Pro. of Symp. on Disc. Alg. (SODA)","author":"Karger David","year":"1993","unstructured":"[Kar93a] David Karger . Global min-cuts in RNC and other ramifications of a simple mincut algorithm . In Pro. of Symp. on Disc. Alg. (SODA) , pages 21 -- 30 , 01 1993 . [Kar93a] David Karger. Global min-cuts in RNC and other ramifications of a simple mincut algorithm. In Pro. of Symp. on Disc. Alg. (SODA), pages 21--30, 01 1993."},{"key":"e_1_3_2_1_34_1","first-page":"21","volume-title":"Pro. of Symp. on Disc. Alg. (SODA)","author":"Karger David R.","year":"1993","unstructured":"[Kar93b] David R. Karger . Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm . In Pro. of Symp. on Disc. Alg. (SODA) , pages 21 -- 30 , 1993 . [Kar93b] David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm. In Pro. of Symp. on Disc. Alg. (SODA), pages 21--30, 1993."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_3_2_1_36_1","first-page":"424","volume-title":"Pro. of Symp. on Disc. Alg. (SODA)","author":"Karger David R.","year":"1994","unstructured":"[Kar94b] David R. Karger . Using randomized sparsification to approximate minimum cuts . In Pro. of Symp. on Disc. Alg. (SODA) , pages 424 -- 432 , 1994 . [Kar94b] David R. Karger. Using randomized sparsification to approximate minimum cuts. In Pro. of Symp. on Disc. Alg. (SODA), pages 424--432, 1994."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_42_1","first-page":"665","volume-title":"Proc. of the Symp. on Theory of Comp. (STOC)","author":"Mikkel Thorup Kawarabayashi","year":"2015","unstructured":"[KT15] Ken-ichi Kawarabayashi and Mikkel Thorup . Deterministic global minimum cut of a simple graph in near-linear time . In Proc. of the Symp. on Theory of Comp. (STOC) , pages 665 -- 674 , 2015 . [KT15] Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic global minimum cut of a simple graph in near-linear time. In Proc. of the Symp. on Theory of Comp. (STOC), pages 665--674, 2015."},{"key":"e_1_3_2_1_43_1","volume-title":"Proc. of the Symp. on Theory of Comp. (STOC)","author":"Lacki Jakub","year":"2020","unstructured":"[LMOS20] Jakub Lacki , Slobodan Mitrovic , Krzysztof Onak , and Piotr Sankowski . Walking randomly, massively, and efficiently . In Proc. of the Symp. on Theory of Comp. (STOC) , 2020 . [LMOS20] Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Proc. of the Symp. on Theory of Comp. (STOC), 2020."},{"key":"e_1_3_2_1_44_1","first-page":"85","volume-title":"Proc. of the Symp. on Parallel Alg. and Arch. (SPAA)","author":"Lattanzi Silvio","year":"2011","unstructured":"[LMSV11] Silvio Lattanzi , Benjamin Moseley , Siddharth Suri , and Sergei Vassilvitskii . Filtering : a method for solving graph problems in mapreduce . In Proc. of the Symp. on Parallel Alg. and Arch. (SPAA) , pages 85 -- 94 , 2011 . [LMSV11] Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proc. of the Symp. on Parallel Alg. and Arch. (SPAA), pages 85--94, 2011."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185411"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935799"},{"key":"e_1_3_2_1_47_1","volume-title":"Hadoop: The Definitive Guide","author":"White Tom","year":"2012","unstructured":"[Whi12] Tom White . Hadoop: The Definitive Guide . O'Reilly Media, Inc. , 2012 . [Whi12] Tom White. Hadoop: The Definitive Guide. O'Reilly Media, Inc., 2012."},{"key":"e_1_3_2_1_48_1","volume-title":"2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud)","author":"Zaharia Matei","year":"2010","unstructured":"[ZCF+10] Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . Spark : Cluster computing with working sets . In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud) , 2010 . [ZCF+10] Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2010."}],"event":{"name":"PODC '20: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '20"},"container-title":["Proceedings of the 39th Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405737","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3405737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:50Z","timestamp":1750197770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":48,"alternative-id":["10.1145\/3382734.3405737","10.1145\/3382734"],"URL":"https:\/\/doi.org\/10.1145\/3382734.3405737","relation":{},"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"2020-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}