{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:52:40Z","timestamp":1752231160205,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-2103483"],"award-info":[{"award-number":["CCF-2103483"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538574","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"273-286","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient"],"prefix":"10.1145","author":[{"given":"Zheqi","family":"Shen","sequence":"first","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Zijin","family":"Wan","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]},{"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"UC Riverside, Riverside, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"volume-title":"https:\/\/www.openstreetmap.org\/","year":"2010","key":"e_1_3_2_1_1_1","unstructured":"Openstreetmap \u00a9 openstreetmap contributors. https:\/\/www.openstreetmap.org\/ , 2010 . Openstreetmap \u00a9 openstreetmap contributors. https:\/\/www.openstreetmap.org\/, 2010."},{"key":"e_1_3_2_1_2_1","volume-title":"The data locality of work stealing. Theoretical Computer Science (TCS), 35(3)","author":"Acar U. A.","year":"2002","unstructured":"U. A. Acar , G. E. Blelloch , and R. D. Blumofe . The data locality of work stealing. Theoretical Computer Science (TCS), 35(3) , 2002 . U. A. Acar, G. E. Blelloch, and R. D. Blumofe. The data locality of work stealing. Theoretical Computer Science (TCS), 35(3), 2002."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0175-7"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612688"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.03.013"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935767"},{"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","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Blelloch G. E.","year":"2008","unstructured":"G. E. Blelloch , R. A. Chowdhury , P. B. Gibbons , V. Ramachandran , S. Chen , and M. Kozuch . Provably good multicore cache performance for divide-and-conquer algorithms . In ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2008 . G. E. Blelloch, R. A. Chowdhury, P. B. Gibbons, V. Ramachandran, S. Chen, and M. Kozuch. Provably good multicore cache performance for divide-and-conquer algorithms. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145840"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989553"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007912.1007948"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210380"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402819"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400255"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_3_2_1_20_1","volume-title":"Pipelining with futures. Theory of Computing Systems (TOCS), 32(3)","author":"Blelloch G. E.","year":"1999","unstructured":"G. E. Blelloch and M. Reid-Miller . Pipelining with futures. Theory of Computing Systems (TOCS), 32(3) , 1999 . G. E. Blelloch and M. Reid-Miller. Pipelining with futures. Theory of Computing Systems (TOCS), 32(3), 1999."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312024"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010104"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087586"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.04.008"},{"key":"e_1_3_2_1_27_1","volume-title":"Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4)","author":"Cole R.","year":"2017","unstructured":"R. Cole and V. Ramachandran . Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4) , 2017 . R. Cole and V. Ramachandran. Resource oblivious sorting on multicores. ACM Transactions on Parallel Computing (TOPC), 3(4), 2017."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.46"},{"key":"e_1_3_2_1_30_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms ( 3 rd edition). MIT Press , 2009 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009.","edition":"3"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055823"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_9"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484257"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523733"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB), 13(9)","author":"Dhulipala L.","year":"2020","unstructured":"L. Dhulipala , C. McGuffey , H. Kang , Y. Gu , G. E. Blelloch , P. B. Gibbons , and J. Shun . Semi-asymmetric parallel graph algorithms for nvrams . Proceedings of the VLDB Endowment (PVLDB), 13(9) , 2020 . L. Dhulipala, C. McGuffey, H. Kang, Y. Gu, G. E. Blelloch, P. B. Gibbons, and J. Shun. Semi-asymmetric parallel graph algorithms for nvrams. Proceedings of the VLDB Endowment (PVLDB), 13(9), 2020."},{"key":"e_1_3_2_1_37_1","volume-title":"Numerische mathematik, 1(1)","author":"Dijkstra E. W.","year":"1959","unstructured":"E. W. Dijkstra . A note on two problems in connexion with graphs. Numerische mathematik, 1(1) , 1959 . E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 1959."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935797"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461782"},{"key":"e_1_3_2_1_40_1","volume-title":"Contention in shared memory algorithms. Journal of the ACM (JACM), 44(6):779--805","author":"Dwork C.","year":"1997","unstructured":"C. Dwork , M. Herlihy , and O. Waarts . Contention in shared memory algorithms. Journal of the ACM (JACM), 44(6):779--805 , 1997 . C. Dwork, M. Herlihy, and O. Waarts. Contention in shared memory algorithms. Journal of the ACM (JACM), 44(6):779--805, 1997."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.79"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.140"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1053"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/70082.68188"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210395"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.9"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612697"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_3_2_1_49_1","volume-title":"A parallel graph coloring heuristic. 14(3):654--669","author":"Jones M. T.","year":"1993","unstructured":"M. T. Jones and P. E. Plassmann . A parallel graph coloring heuristic. 14(3):654--669 , 1993 . M. T. Jones and P. E. Plassmann. A parallel graph coloring heuristic. 14(3):654--669, 1993."},{"key":"e_1_3_2_1_50_1","volume-title":"More parallelism in dijkstra's single-source shortest path algorithm. arXiv preprint arXiv:1903.12085","author":"Kainer M.","year":"2019","unstructured":"M. Kainer and J. L. Tr\"aff. More parallelism in dijkstra's single-source shortest path algorithm. arXiv preprint arXiv:1903.12085 , 2019 . M. Kainer and J. L. Tr\"aff. More parallelism in dijkstra's single-source shortest path algorithm. arXiv preprint arXiv:1903.12085, 2019."},{"key":"e_1_3_2_1_51_1","volume-title":"Executing dynamic data-graph computations deterministically using chromatic scheduling. ACM Transactions on Parallel Computing (TOPC), 3(1):1--31","author":"Kaler T.","year":"2016","unstructured":"T. Kaler , W. Hasenplaugh , T. B. Schardl , and C. E. Leiserson . Executing dynamic data-graph computations deterministically using chromatic scheduling. ACM Transactions on Parallel Computing (TOPC), 3(1):1--31 , 2016 . T. Kaler, W. Hasenplaugh, T. B. Schardl, and C. E. Leiserson. Executing dynamic data-graph computations deterministically using chromatic scheduling. ACM Transactions on Parallel Computing (TOPC), 3(1):1--31, 2016."},{"key":"e_1_3_2_1_52_1","first-page":"176","volume-title":"International Conference on Parallel Processing and Applied Mathematics","author":"Krusche P.","year":"2009","unstructured":"P. Krusche and A. Tiskin . Parallel longest increasing subsequences in scalable time and memory . In International Conference on Parallel Processing and Applied Mathematics , pages 176 -- 185 . Springer , 2009 . P. Krusche and A. Tiskin. Parallel longest increasing subsequences in scalable time and memory. In International Conference on Parallel Processing and Applied Mathematics, pages 176--185. Springer, 2009."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810521"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_2_1_55_1","volume-title":"Encyclopedia of Parallel Computing","author":"Leiserson C. E.","year":"2011","unstructured":"C. E. Leiserson . Cilk. In D. A. Padua, editor, Encyclopedia of Parallel Computing . Springer , 2011 . C. E. Leiserson. Cilk. In D. A. Padua, editor, Encyclopedia of Parallel Computing. Springer, 2011."},{"key":"e_1_3_2_1_56_1","first-page":"15","article-title":"A simple parallel algorithm for the maximal independent set problem","author":"Luby M.","year":"1986","unstructured":"M. Luby . A simple parallel algorithm for the maximal independent set problem . SIAM J. on Computing , 15 , 1986 . M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing, 15, 1986.","journal-title":"SIAM J. on Computing"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"e_1_3_2_1_58_1","first-page":"7","volume-title":"International Conference in Networks, Parallel and Distributed Processing and Applications","author":"Nakashima T.","year":"2002","unstructured":"T. Nakashima and A. Fujiwara . Parallel algorithms for patience sorting and longest increasing subsequence . In International Conference in Networks, Parallel and Distributed Processing and Applications , pages 7 -- 12 , 2002 . T. Nakashima and A. Fujiwara. Parallel algorithms for patience sorting and longest increasing subsequence. In International Conference in Networks, Parallel and Distributed Processing and Applications, pages 7--12, 2002."},{"key":"e_1_3_2_1_59_1","volume-title":"A cost optimal parallel algorithm for patience sorting. Parallel processing letters, 16(01):39--51","author":"Nakashima T.","year":"2006","unstructured":"T. Nakashima and A. Fujiwara . A cost optimal parallel algorithm for patience sorting. Parallel processing letters, 16(01):39--51 , 2006 . T. Nakashima and A. Fujiwara. A cost optimal parallel algorithm for patience sorting. Parallel processing letters, 16(01):39--51, 2006."},{"key":"e_1_3_2_1_60_1","first-page":"82","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Pan X.","year":"2015","unstructured":"X. Pan , D. Papailiopoulos , S. Oymak , B. Recht , K. Ramchandran , and M. I. Jordan . Parallel correlation clustering on big graphs . In Advances in Neural Information Processing Systems (NIPS) , pages 82 -- 90 , 2015 . X. Pan, D. Papailiopoulos, S. Oymak, B. Recht, K. Ramchandran, and M. I. Jordan. Parallel correlation clustering on big graphs. In Advances in Neural Information Processing Systems (NIPS), pages 82--90, 2015."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/11751649_2"},{"key":"e_1_3_2_1_62_1","volume-title":"Many sequential iterative algorithms can be parallel and (nearly) work-efficient. arXiv preprint arXiv:2205.13077","author":"Shen Z.","year":"2022","unstructured":"Z. Shen , Z. Wan , Y. Gu , and Y. Sun . Many sequential iterative algorithms can be parallel and (nearly) work-efficient. arXiv preprint arXiv:2205.13077 , 2022 . Z. Shen, Z. Wan, Y. Gu, and Y. Sun. Many sequential iterative algorithms can be parallel and (nearly) work-efficient. arXiv preprint arXiv:2205.13077, 2022."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722159"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975499.13"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378756"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9830-z"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"}],"event":{"name":"SPAA '22: 34th 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":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538574","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:08Z","timestamp":1750191128000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":70,"alternative-id":["10.1145\/3490148.3538574","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538574","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}