{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:08:09Z","timestamp":1755907689011,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3626183.3659963","type":"proceedings-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T18:23:04Z","timestamp":1717525384000},"page":"395-402","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Connected Components in Linear Work and Near-Optimal Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1149-413X","authenticated-orcid":false,"given":"Alireza","family":"Farhadi","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2776-2120","authenticated-orcid":false,"given":"Sixue Cliff","family":"Liu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5605-1048","authenticated-orcid":false,"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. 2018. Parallel Graph Connectivity in Log Diameter Rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7--9, 2018. 674--685."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331596"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676869"},{"key":"e_1_3_2_1_4_1","volume-title":"Optimal Deterministic Massively Parallel Connectivity on Forests. In ACM-SIAM Symposium on Discrete Algorithms (SODA23)","author":"Balliu Alkida","year":"2023","unstructured":"Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. 2023. Optimal Deterministic Massively Parallel Connectivity on Forests. In ACM-SIAM Symposium on Discrete Algorithms (SODA23)."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65958"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_7_1","volume-title":"Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni. 2019. Near-Optimal Massively Parallel Graph Connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9--12, 2019. 1615--1636."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520055"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80003-0"},{"key":"e_1_3_2_1_11_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Paul","year":"1960","unstructured":"Paul ErdHo s, Alfr\u00e9d R\u00e9nyi, et al. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, Vol. 5, 1 (1960), 17--60.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220066"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/885651.781046"},{"key":"e_1_3_2_1_14_1","volume-title":"ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings. 374--383","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings. 374--383."},{"key":"e_1_3_2_1_15_1","volume-title":"Waste Makes Haste: Tight Bounds for Loose Parallel Sorting. In 33rd Annual Symposium on Foundations of Computer Science","author":"Hagerup Torben","year":"1992","unstructured":"Torben Hagerup and Rajeev Raman. 1992. Waste Makes Haste: Tight Bounds for Loose Parallel Sorting. In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24--27 October 1992. IEEE Computer Society, 628--637."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400249"},{"volume-title":"Proceedings of the 16th International Conference on Database Systems for Advanced Applications. 311--322","author":"Fragkiskos","key":"e_1_3_2_1_21_1","unstructured":"Fragkiskos D. Malliaros and Vasileios Megalooikonomou. 2011. Expansion Properties of Large Social Graphs. In Proceedings of the 16th International Conference on Database Systems for Advanced Applications. 311--322."},{"key":"e_1_3_2_1_22_1","unstructured":"John H Reif. 1984. Optimal Parallel Algorithms for Graph Connectivity. Technical Report. HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3232536"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90033-0"}],"event":{"name":"SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Nantes France","acronym":"SPAA '24"},"container-title":["Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659963","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626183.3659963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T16:24:48Z","timestamp":1755879888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":26,"alternative-id":["10.1145\/3626183.3659963","10.1145\/3626183"],"URL":"https:\/\/doi.org\/10.1145\/3626183.3659963","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}