{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T07:36:44Z","timestamp":1768030604964,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":91,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,11]],"date-time":"2018-07-11T00:00:00Z","timestamp":1531267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1408940, CCF-1533858, CCF-1629444."],"award-info":[{"award-number":["CCF-1408940, CCF-1533858, CCF-1629444."]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,11]]},"DOI":"10.1145\/3210377.3210414","type":"proceedings-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T17:46:44Z","timestamp":1531417604000},"page":"393-404","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable"],"prefix":"10.1145","author":[{"given":"Laxman","family":"Dhulipala","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73035"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_4_1","volume-title":"A $mathsfP$-complete problem and approximations to it. Technical report","author":"Anderson R.","year":"1984","unstructured":"R. Anderson and E. W. Mayr . A $mathsfP$-complete problem and approximations to it. Technical report , 1984 . R. Anderson and E. W. Mayr. A $mathsfP$-complete problem and approximations to it. Technical report, 1984."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2006.06.001"},{"key":"e_1_3_2_1_6_1","volume-title":"The GAP benchmark suite. CoRR, abs\/1508.03619","author":"Beamer S.","year":"2015","unstructured":"S. Beamer , K. Asanovic , and D. A. Patterson . The GAP benchmark suite. CoRR, abs\/1508.03619 , 2015 . S. Beamer, K. Asanovic, and D. A. Patterson. The GAP benchmark suite. CoRR, abs\/1508.03619, 2015."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00081"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_66"},{"key":"e_1_3_2_1_9_1","volume-title":"Synthesis of Parallel Algorithms","author":"Blelloch G. E.","year":"1993","unstructured":"G. E. Blelloch . Prefix sums and their applications . Synthesis of Parallel Algorithms , 1993 . G. E. Blelloch. Prefix sums and their applications. Synthesis of Parallel Algorithms, 1993."},{"key":"e_1_3_2_1_10_1","volume-title":"Introduction to parallel algorithms 15--853: Algorithms in the real world","author":"Blelloch G. E.","year":"2018","unstructured":"G. E. Blelloch and L. Dhulipala . Introduction to parallel algorithms 15--853: Algorithms in the real world . 2018 . G. E. Blelloch and L. Dhulipala. Introduction to parallel algorithms 15--853: Algorithms in the real world. 2018."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935766"},{"key":"e_1_3_2_1_13_1","volume-title":"ICALP","author":"Blelloch G. E.","year":"2017","unstructured":"G. E. Blelloch , Y. Gu , and Y. Sun . A new efficient construction on probabilistic tree embeddings . In ICALP , 2017 . G. E. Blelloch, Y. Gu, and Y. Sun. A new efficient construction on probabilistic tree embeddings. In ICALP, 2017."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989497"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312024"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_1_18_1","volume-title":"O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Pvr\u00edrodovved. Spol. v Brnve III, 3","author":"Borruvka O.","year":"1926","unstructured":"O. Borruvka . O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Pvr\u00edrodovved. Spol. v Brnve III, 3 , 1926 . O. Borruvka. O jist\u00e9m probl\u00e9mu minim\u00e1ln\u00edm. Pr\u00e1ce Mor. Pvr\u00edrodovved. Spol. v Brnve III, 3, 1926."},{"key":"e_1_3_2_1_19_1","volume-title":"A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2)","author":"Brandes U.","year":"2001","unstructured":"U. Brandes . A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2) , 2001 . U. Brandes. A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2), 2001."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/237502.237563"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2005.100"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCC-SmartCity-DSS.2016.0037"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","DOI":"10.2172\/889876","volume-title":"A divide-and-conquer algorithm for identifying strongly connected components","author":"Coppersmith D.","year":"2003","unstructured":"D. Coppersmith , L. Fleischer , B. Hendrickson , and A. Pinar . A divide-and-conquer algorithm for identifying strongly connected components . 2003 . D. Coppersmith, L. Fleischer, B. Hendrickson, and A. Pinar. A divide-and-conquer algorithm for identifying strongly connected components. 2003."},{"key":"e_1_3_2_1_25_1","volume-title":"Introduction to Algorithms (3. ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms (3. ed.) . MIT Press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009."},{"key":"e_1_3_2_1_26_1","volume-title":"FAST","author":"Da Zheng D. M.","year":"2015","unstructured":"D. M. Da Zheng , R. Burns , J. Vogelstein , C. E. Priebe , and A. S. Szalay . Flashgraph: Processing billion-node graphs on an array of commodity SSDs . In FAST , 2015 . D. M. Da Zheng, R. Burns, J. Vogelstein, C. E. Priebe, and A. S. Szalay. Flashgraph: Processing billion-node graphs on an array of commodity SSDs. In FAST, 2015."},{"key":"e_1_3_2_1_27_1","volume-title":"Big Data","author":"Dasari N. S.","year":"2014","unstructured":"N. S. Dasari , R. Desh , and M. Zubair . ParK: An efficient algorithm for k -core decomposition on multicore processors . In Big Data , 2014 . N. S. Dasari, R. Desh, and M. Zubair. ParK: An efficient algorithm for k -core decomposition on multicore processors. In Big Data, 2014."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2141702.2141714"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188926"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175445"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/645612.663154"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90164-0"},{"key":"e_1_3_2_1_36_1","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . PowerGraph: Distributed graph-parallel computation on natural graphs . In OSDI , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. In OSDI, 2012."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567634.2567635"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-completeness Theory","author":"Greenlaw R.","year":"1995","unstructured":"R. Greenlaw , H. J. Hoover , and W. L. Ruzzo . Limits to Parallel Computation: P-completeness Theory . Oxford University Press, Inc. , 1995 . R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-completeness Theory. Oxford University Press, Inc., 1995."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503246"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90141-9"},{"key":"e_1_3_2_1_44_1","volume-title":"Introduction to Parallel Algorithms","author":"Jaja J.","year":"1992","unstructured":"J. Jaja . Introduction to Parallel Algorithms . Addison-Wesley Professional , 1992 . J. Jaja. Introduction to Parallel Algorithms. Addison-Wesley Professional, 1992."},{"key":"e_1_3_2_1_45_1","volume-title":"BigSparse: High-performance external graph analytics. CoRR, abs\/1710.07736","author":"Jun S. W.","year":"2017","unstructured":"S. W. Jun , A. Wright , S. Zhang , S. Xu , and Arvind. BigSparse: High-performance external graph analytics. CoRR, abs\/1710.07736 , 2017 . S. W. Jun, A. Wright, S. Zhang, S. Xu, and Arvind. BigSparse: High-performance external graph analytics. CoRR, abs\/1710.07736, 2017."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2017.151"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"e_1_3_2_1_48_1","volume-title":"Handbook of theoretical computer science (vol. a)","author":"Karp R. M.","year":"1990","unstructured":"R. M. Karp and V. Ramachandran . Handbook of theoretical computer science (vol. a) . chapter Parallel Algorithms for Shared-memory Machines. MIT Press , Cambridge, MA, USA , 1990 . R. M. Karp and V. Ramachandran. Handbook of theoretical computer science (vol. a). chapter Parallel Algorithms for Shared-memory Machines. MIT Press, Cambridge, MA, USA, 1990."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808690"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588563"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_1_52_1","volume-title":"UAI","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . GraphLab: A new parallel framework for machine learning . In UAI , 2010 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new parallel framework for machine learning. In UAI, 2010."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926287"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_2_1_57_1","first-page":"47","article-title":"Parallel ear decomposition search (EDS) and st-numbering in graphs","author":"Maon Y.","year":"1986","unstructured":"Y. Maon , B. Schieber , and U. Vishkin . Parallel ear decomposition search (EDS) and st-numbering in graphs . Theoretical Computer Science , 47 , 1986 . Y. Maon, B. Schieber, and U. Vishkin. Parallel ear decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47, 1986.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.03.007"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1561\/106.00000003"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_64_1","volume-title":"Mar","author":"Miller G. L.","year":"1992","unstructured":"G. L. Miller and V. Ramachandran . A new graph triconnectivity algorithm and its parallelization. Combinatorica, 12(1) , Mar 1992 . G. L. Miller and V. Ramachandran. A new graph triconnectivity algorithm and its parallelization. Combinatorica, 12(1), Mar 1992."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145842"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.79"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700371065"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.5555\/647637.733198"},{"key":"e_1_3_2_1_70_1","volume-title":"Synthesis of Parallel Algorithms","author":"Ramachandran V.","year":"1993","unstructured":"V. Ramachandran . Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity . In Synthesis of Parallel Algorithms , 1993 . V. Ramachandran. Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. In Synthesis of Parallel Algorithms, 1993."},{"key":"e_1_3_2_1_71_1","volume-title":"Parallel local algorithms for core, truss, and nucleus decompositions. arXiv preprint arXiv:1704.00386","author":"Sariyuce A. E.","year":"2017","unstructured":"A. E. Sariyuce , C. Seshadhri , and A. Pinar . Parallel local algorithms for core, truss, and nucleus decompositions. arXiv preprint arXiv:1704.00386 , 2017 . A. E. Sariyuce, C. Seshadhri, and A. Pinar. Parallel local algorithms for core, truss, and nucleus decompositions. arXiv preprint arXiv:1704.00386, 2017."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378560"},{"key":"e_1_3_2_1_73_1","volume-title":"Network structure and minimum degree. Soc. Networks, 5(3)","author":"Seidman S. B.","year":"1983","unstructured":"S. B. Seidman . Network structure and minimum degree. Soc. Networks, 5(3) , 1983 . S. B. Seidman. Network structure and minimum degree. Soc. Networks, 5(3), 1983."},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2659480.2659494"},{"key":"e_1_3_2_1_75_1","volume-title":"Algorithms","author":"Shiloach Y.","year":"1982","unstructured":"Y. Shiloach and U. Vishkin . An $O(\u0142og n)$ parallel connectivity algorithm. J . Algorithms , 1982 . Y. Shiloach and U. Vishkin. An $O(\u0142og n)$ parallel connectivity algorithm. J. Algorithms, 1982."},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486189"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312018"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612692"},{"key":"e_1_3_2_1_80_1","unstructured":"J. Shun L. Dhulipala and G. E. Blelloch. Smaller and faster: Parallel processing of compressed graphs with Ligra  J. Shun L. Dhulipala and G. E. Blelloch. Smaller and faster: Parallel processing of compressed graphs with Ligra"},{"key":"e_1_3_2_1_81_1","volume-title":"DCC","year":"2015","unstructured":". In DCC , 2015 . . In DCC, 2015."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2014.7116914"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_3_2_1_85_1","volume-title":"Supercomputing for Web Graph Analytics","author":"Slota G. M.","year":"2015","unstructured":"G. M. Slota , S. Rajamanickam , and K. Madduri . Supercomputing for Web Graph Analytics . Apr 2015 . G. M. Slota, S. Rajamanickam, and K. Madduri. Supercomputing for Web Graph Analytics. Apr 2015."},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.93"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159696"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000056"},{"key":"e_1_3_2_1_91_1","volume-title":"KIT","author":"Zhou W.","year":"2017","unstructured":"W. Zhou . A practical scalable shared-memory parallel algorithm for computing minimum spanning trees. Master's thesis , KIT , 2017 . W. Zhou. A practical scalable shared-memory parallel algorithm for computing minimum spanning trees. Master's thesis, KIT, 2017."}],"event":{"name":"SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Vienna Austria","acronym":"SPAA '18","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"]},"container-title":["Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210414","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210414","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210377.3210414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:20Z","timestamp":1750210760000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210377.3210414"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,11]]},"references-count":91,"alternative-id":["10.1145\/3210377.3210414","10.1145\/3210377"],"URL":"https:\/\/doi.org\/10.1145\/3210377.3210414","relation":{},"subject":[],"published":{"date-parts":[[2018,7,11]]},"assertion":[{"value":"2018-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}