{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T22:06:49Z","timestamp":1775254009244,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,6,21]],"date-time":"2014-06-21T00:00:00Z","timestamp":1403308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1314590"],"award-info":[{"award-number":["CCF-1314590"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,6,21]]},"DOI":"10.1145\/2612669.2612692","type":"proceedings-article","created":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T14:23:03Z","timestamp":1404224583000},"page":"143-153","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["A simple and practical linear-work parallel algorithm for connectivity"],"prefix":"10.1145","author":[{"given":"Julian","family":"Shun","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Laxman","family":"Dhulipala","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Guy","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2014,6,21]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"783","volume-title":"ICPP","author":"Agrawal A.","year":"1987","unstructured":"A. Agrawal , L. Nekludova , and W. Lim . A parallel O(logN) algorithm for finding connected components in planar images . In ICPP , pages 783 -- 786 , 1987 . A. Agrawal, L. Nekludova, and W. Lim. A parallel O(logN) algorithm for finding connected components in planar images. In ICPP, pages 783--786, 1987."},{"key":"e_1_3_2_1_2_1","first-page":"177","volume-title":"ICPP","author":"Awerbuch B.","year":"1983","unstructured":"B. Awerbuch and Y. Shiloach . New connectivity and MSF algorithms for Ultracomputer and PRAM . In ICPP , pages 177 -- 187 , 1983 . B. Awerbuch and Y. Shiloach. New connectivity and MSF algorithms for Ultracomputer and PRAM. In ICPP, pages 177--187, 1983."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.03.011"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2005.55"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0079"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2011.6152655"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_10"},{"key":"e_1_3_2_1_8_1","first-page":"1","volume-title":"Supercomputing","author":"Beamer S.","year":"2012","unstructured":"S. Beamer , K. Asanovi\u0107 , and D. Patterson . Direction-optimizing breadth-first search . In Supercomputing , pages 12: 1 -- 12 :10, 2012 . S. Beamer, K. Asanovi\u0107, and D. Patterson. Direction-optimizing breadth-first search. In Supercomputing, pages 12:1--12:10, 2012."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09766-4_225"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989496"},{"key":"e_1_3_2_1_11_1","first-page":"277","volume-title":"The Computer Science and Engineering Handbook","author":"Blelloch G. E.","year":"1997","unstructured":"G. E. Blelloch and B. M. Maggs . Parallel algorithms . In The Computer Science and Engineering Handbook , pages 277 -- 315 . 1997 . G. E. Blelloch and B. M. Maggs. Parallel algorithms. In The Computer Science and Engineering Handbook, pages 277--315. 1997."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/648138.746654"},{"key":"e_1_3_2_1_13_1","first-page":"631","volume-title":"High Performance Computing & Simulation","author":"Caceres E.","year":"2010","unstructured":"E. Caceres , H. Mongelli , C. Nishibe , and S. W. Song . Experimental results of a coarse-grained parallel algorithm for spanning tree and connected components . In High Performance Computing & Simulation , pages 631 -- 637 , 2010 . E. Caceres, H. Mongelli, C. Nishibe, and S. W. Song. Experimental results of a coarse-grained parallel algorithm for spanning tree and connected components. In High Performance Computing & Simulation, pages 631--637, 2010."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/358628.358650"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1016"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237563"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90019-X"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220066"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_3_2_1_21_1","first-page":"43","volume-title":"Parallel Algorithms: 3rd DIMACS Implementation Challenge","author":"Goddard S.","year":"1995","unstructured":"S. Goddard , S. Kumar , and J. F. Prins . Connected components algorithms for mesh-connected parallel computers . In Parallel Algorithms: 3rd DIMACS Implementation Challenge , pages 43 -- 58 , 1995 . S. Goddard, S. Kumar, and J. F. Prins. Connected components algorithms for mesh-connected parallel computers. In Parallel Algorithms: 3rd DIMACS Implementation Challenge, pages 43--58, 1995."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181021"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1146"},{"key":"e_1_3_2_1_25_1","first-page":"477","volume-title":"Supercomputing","author":"Hambrusch S.","year":"1988","unstructured":"S. Hambrusch and L. TeWinkel . A study of connected component labeling algorithms on the MPP . In Supercomputing , pages 477 -- 483 , 1988 . S. Hambrusch and L. TeWinkel. A study of connected component labeling algorithms on the MPP. In Supercomputing, pages 477--483, 1988."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214077"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2010.07.002"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359141"},{"key":"e_1_3_2_1_29_1","volume-title":"Parallel implementation of algorithms for finding connected components in graphs","author":"Hsu T.-S.","year":"1997","unstructured":"T.-S. Hsu , V. Ramachandran , and N. Dean . Parallel implementation of algorithms for finding connected components in graphs , 1997 . T.-S. Hsu, V. Ramachandran, and N. Dean. Parallel implementation of algorithms for finding connected components in graphs, 1997."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1009"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1291"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979325247X"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/647892.739745"},{"key":"e_1_3_2_1_35_1","first-page":"1","volume-title":"Parallel Algorithms: 3rd DIMACS Implementation Challenge","author":"Krishnamurthy A.","year":"1994","unstructured":"A. Krishnamurthy , S. S. Lumetta , D. E. Culler , and K. Yelick . Connected components on distributed memory machines . In Parallel Algorithms: 3rd DIMACS Implementation Challenge , pages 1 -- 21 , 1994 . A. Krishnamurthy, S. S. Lumetta, D. E. Culler, and K. Yelick. Connected components on distributed memory machines. In Parallel Algorithms: 3rd DIMACS Implementation Challenge, pages 1--21, 1994."},{"key":"e_1_3_2_1_36_1","volume-title":"Efficient parallel algorithms for graph problems. Algorithmica, 5(1--4)","author":"Kruskal C.","year":"1990","unstructured":"C. Kruskal , L. Rudolph , and M. Snir . Efficient parallel algorithms for graph problems. Algorithmica, 5(1--4) , 1990 . C. Kruskal, L. Rudolph, and M. Snir. Efficient parallel algorithms for graph problems. Algorithmica, 5(1--4), 1990."},{"key":"e_1_3_2_1_37_1","first-page":"31","volume-title":"Operating System Design and Implementation","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola , G. E. Blelloch , and C. Guestrin . GraphChi: Large-scale graph computation on just a PC . In Operating System Design and Implementation , pages 31 -- 46 , 2012 . A. Kyrola, G. E. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In Operating System Design and Implementation, pages 31--46, 2012."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_11"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-010-0405-3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810534"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90034-V"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90131-4"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267822"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.79"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700371065"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/72935.72952"},{"key":"e_1_3_2_1_51_1","first-page":"212","volume-title":"ISAAC","author":"Poon C. K.","year":"1997","unstructured":"C. K. Poon and V. Ramachandran . A randomized linear work EREW PRAM algorithm to find a minimum spanning forest . In ISAAC , pages 212 -- 222 , 1997 . C. K. Poon and V. Ramachandran. A randomized linear work EREW PRAM algorithm to find a minimum spanning forest. In ISAAC, pages 212--222, 1997."},{"key":"e_1_3_2_1_52_1","volume-title":"Optimal parallel algorithms for integer sorting and graph connectivity. TR-08--85","author":"Reif J.","year":"1985","unstructured":"J. Reif . Optimal parallel algorithms for integer sorting and graph connectivity. TR-08--85 , Harvard University , 1985 . J. Reif. Optimal parallel algorithms for integer sorting and graph connectivity. TR-08--85, Harvard University, 1985."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612687"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486189"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470817"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90019-2"}],"event":{"name":"SPAA '14: 26th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Prague Czech Republic","acronym":"SPAA '14","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture"]},"container-title":["Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2612669.2612692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2612669.2612692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:34Z","timestamp":1750230094000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2612669.2612692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,21]]},"references-count":59,"alternative-id":["10.1145\/2612669.2612692","10.1145\/2612669"],"URL":"https:\/\/doi.org\/10.1145\/2612669.2612692","relation":{},"subject":[],"published":{"date-parts":[[2014,6,21]]},"assertion":[{"value":"2014-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}