{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:46Z","timestamp":1777954606058,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":43,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743322","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"299-313","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Batch-Dynamic Algorithms for Spanners, and Extensions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4213-9898","authenticated-orcid":false,"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7599-3662","authenticated-orcid":false,"given":"Jaehyun","family":"Koo","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"European Symposium on Algorithms (ESA)","author":"Acar Umut","year":"2020","unstructured":"[AA20] Umut Acar and Daniel Anderson. Parallel batch-dynamic trees via change propagation. In European Symposium on Algorithms (ESA), 2020."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323196"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659976"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366823"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.100253"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_10"},{"key":"e_1_3_2_1_10_1","volume-title":"A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1--51","author":"Bernstein Aaron","year":"2021","unstructured":"[BFH21] Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms (TALG), 17(4):1--51, 2021."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_12_1","first-page":"17","volume-title":"24th Annual European Symposium on Algorithms (ESA 2016","author":"Bodwin Greg","year":"2016","unstructured":"[BK16] Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. In 24th Annual European Symposium on Algorithms (ESA 2016), pages 17--1. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2016."},{"key":"e_1_3_2_1_13_1","volume-title":"Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8(4):1--51","author":"Baswana Surender","year":"2012","unstructured":"[BKS12] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8(4):1--51, 2012."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_15_1","volume-title":"The parallel evaluation of general arithmetic expressions. Journal of the ACM (JACM), 21(2):201--206","author":"Brent Richard P","year":"1974","unstructured":"[Bre74] Richard P Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM (JACM), 21(2):201--206, 1974."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347205"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536451"},{"key":"e_1_3_2_1_21_1","first-page":"17","volume-title":"30th Annual European Symposium on Algorithms (ESA 2022","author":"Bhattacharya Sayan","year":"2022","unstructured":"[BSS22] Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. In 30th Annual European Symposium on Algorithms (ESA 2022), pages 17--1. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2022."},{"key":"e_1_3_2_1_22_1","series-title":"LIPIcs","first-page":"1","volume-title":"Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary","author":"Bernstein Aaron","year":"2022","unstructured":"[BvdBG+22] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 20:1--20:20. Schloss Dagstuhl -Leibniz-Zentrum f\u00fcr Informatik, 2022."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366822"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_2_1_25_1","volume-title":"Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms (TALG), 7(2):1--17","author":"Elkin Michael","year":"2011","unstructured":"[Elk11] Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms (TALG), 7(2):1--17, 2011."},{"key":"e_1_3_2_1_26_1","volume-title":"Efficient algorithms for constructing very sparse spanners and emulators. 15(1), nov","author":"Elkin Michael","year":"2018","unstructured":"[EN18a] Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. 15(1), nov 2018."},{"key":"e_1_3_2_1_27_1","volume-title":"Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1--29","author":"Elkin Michael","year":"2018","unstructured":"[EN18b] Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and emulators. ACM Transactions on Algorithms (TALG), 15(1):1--29, 2018."},{"key":"e_1_3_2_1_28_1","first-page":"2936","volume-title":"Proceedings of the Symposium on Theory of Graphs and its Applications","author":"Erd\u0151s Paul","year":"1963","unstructured":"[Erd63] Paul Erd\u0151s. Extremal problems in graph theory. In Proceedings of the Symposium on Theory of Graphs and its Applications, page 2936, 1963."},{"key":"e_1_3_2_1_29_1","volume-title":"An on-line edge-deletion problem. Journal of the ACM(JACM), 28(1):1--4","author":"Even Shimon","year":"1981","unstructured":"[ES81] Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM(JACM), 28(1):1--4, 1981."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316381"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591094"},{"key":"e_1_3_2_1_32_1","first-page":"698","volume-title":"Proceedings 32nd Annual Symposium of Foundations of Computer Science","author":"Gil Joseph","year":"1991","unstructured":"[GMV91] Joseph Gil, Yossi Matias, and Uzi Vishkin. Towards a theory of nearly constant time parallel algorithms. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 698--710. IEEE Computer Society, 1991."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659982"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612676"},{"key":"e_1_3_2_1_36_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018","author":"Lenzen Christoph","year":"2018","unstructured":"[LL18] Christoph Lenzen and Reut Levi. A centralized local algorithm for the sparse spanning graph problem. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 87:1--87:14, 2018."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00287-5"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538584"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_3_2_1_43_1","volume-title":"Approximate distance oracles. Journal of the ACM(JACM), 52(1):1--24","author":"Thorup Mikkel","year":"2005","unstructured":"[TZ05] Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM(JACM), 52(1):1--24, 2005."}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","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 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:00Z","timestamp":1777922340000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":43,"alternative-id":["10.1145\/3694906.3743322","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743322","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}