{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:14Z","timestamp":1750220174740,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"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":[[2022,6,30]]},"abstract":"<jats:p>\n            We study a class of simple algorithms for concurrently computing the connected components of an\n            <jats:italic>n<\/jats:italic>\n            -vertex,\n            <jats:italic>m<\/jats:italic>\n            -edge graph. Our algorithms are easy to implement in either the COMBINING CRCW PRAM or the MPC computing model. For two related algorithms in this class, we obtain \u0398 (lg\n            <jats:italic>n<\/jats:italic>\n            ) step and \u0398 (m lg\n            <jats:italic>n<\/jats:italic>\n            ) work bounds.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            For two others, we obtain\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) step and\n            <jats:italic>O<\/jats:italic>\n            (m lg\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.\n          <\/jats:p>","DOI":"10.1145\/3543546","type":"journal-article","created":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T09:04:34Z","timestamp":1657271074000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Simple Concurrent Connected Components Algorithms"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1327-0985","authenticated-orcid":false,"given":"Sixue Cliff","family":"Liu","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7505-5768","authenticated-orcid":false,"given":"Robert Endre","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/63471"},{"key":"e_1_3_2_3_2","first-page":"674","volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7\u20139, 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\u20139, 2018. 674\u2013685."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676869"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_6_2","article-title":"Near-optimal massively parallel graph connectivity","volume":"1910","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. CoRR abs\/1910.05385 (2019).","journal-title":"CoRR"},{"key":"e_1_3_2_7_2","article-title":"Graph connectivity in log-diameter steps using label propagation","volume":"1808","author":"Burkhardt Paul","year":"2018","unstructured":"Paul Burkhardt. 2018. Graph connectivity in log-diameter steps using label propagation. CoRR abs\/1808.06705 (2018).","journal-title":"CoRR"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"key":"e_1_3_2_9_2","first-page":"43","volume-title":"Parallel Algorithms, Proceedings of a DIMACS Workshop, Brunswick, New Jersey, USA, October 17\u201318, 1994","author":"Goddard Steve","year":"1994","unstructured":"Steve Goddard, Subodh Kumar, and Jan F. Prins. 1994. Connected components algorithms for mesh-connected parallel computers. In Parallel Algorithms, Proceedings of a DIMACS Workshop, Brunswick, New Jersey, USA, October 17\u201318, 1994. 43\u201358."},{"key":"e_1_3_2_10_2","first-page":"16","volume-title":"SPAA","author":"Greiner John","year":"1994","unstructured":"John Greiner. 1994. A comparison of parallel algorithms for connected components. In SPAA. 16\u201325."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359141"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3410463.3414657"},{"key":"e_1_3_2_15_2","first-page":"20","article-title":"Parallel implementation of algorithms for finding connected components in graphs","volume":"30","author":"Hsu Tsan-Sheng","year":"1997","unstructured":"Tsan-Sheng Hsu, Vijaya Ramachandran, and Nathaniel Dean. 1997. Parallel implementation of algorithms for finding connected components in graphs. Parallel Algorithms: Third DIMACS Implementation Challenge, October 17\u201319, 1994 30 (1997), 20.","journal-title":"Parallel Algorithms: Third DIMACS Implementation Challenge, October 17\u201319, 1994"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933108"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1291"},{"key":"e_1_3_2_18_2","first-page":"3:1\u20133:20","volume-title":"2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8\u20139, 2019 - San Diego, CA, USA","author":"Liu S. Cliff","year":"2019","unstructured":"S. Cliff Liu and Robert E. Tarjan. 2019. Simple concurrent labeling algorithms for connected components. In 2nd Symposium on Simplicity in Algorithms, SOSA@SODA 2019, January 8\u20139, 2019 - San Diego, CA, USA. 3:1\u20133:20."},{"key":"e_1_3_2_19_2","article-title":"Connected components on a PRAM in log diameter time","volume":"2003","author":"Liu S. Cliff","year":"2020","unstructured":"S. Cliff Liu, Robert E. Tarjan, and Peilin Zhong. 2020. Connected components on a PRAM in log diameter time. CoRR abs\/2003.00614 (2020). https:\/\/arxiv.org\/abs\/2003.00614.","journal-title":"CoRR"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_2_21_2","volume-title":"15th Workshop on Hot Topics in Operating Systems, HotOS XV, Kartause Ittingen, Switzerland, May 18\u201320, 2015","author":"McSherry Frank","year":"2015","unstructured":"Frank McSherry, Michael Isard, and Derek Gordon Murray. 2015. Scalability! But at what COST? In 15th Workshop on Hot Topics in Operating Systems, HotOS XV, Kartause Ittingen, Switzerland, May 18\u201320, 2015."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_3_2_23_2","volume-title":"Optimal Parallel Algorithms for Graph Connectivity.","author":"Reif John H.","year":"1984","unstructured":"John H. Reif. 1984. Optimal Parallel Algorithms for Graph Connectivity.Technical Report. Harvard University Cambridge, MA, Aiken Computation Lab."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470817"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626410000272"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159696"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976137.5"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543546","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3543546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:47Z","timestamp":1750186847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3543546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3543546"],"URL":"https:\/\/doi.org\/10.1145\/3543546","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}