{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:22:31Z","timestamp":1777965751348,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2119352,CCF-1919223"],"award-info":[{"award-number":["CCF-2119352,CCF-1919223"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743313","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"429-442","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallel Batch-Dynamic Maximal Matching with Constant Work per Update"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0224-9187","authenticated-orcid":false,"given":"Guy E.","family":"Blelloch","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6117-013X","authenticated-orcid":false,"given":"Andrew C.","family":"Brady","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM.","author":"Acar Umut A.","year":"2019","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM."},{"key":"e_1_3_2_1_2_1","volume-title":"European Symposium on Algorithms (ESA).","author":"Acar Umut A.","year":"2020","unstructured":"Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_3_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Anderson Daniel","unstructured":"Daniel Anderson and Guy E. Blelloch. 2021. Parallel Minimum Cuts in O(m log2 n) Work and Low Depth. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400241"},{"key":"e_1_3_2_1_5_1","volume-title":"European Symposium on Algorithms (ESA).","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Shay Solomon. 2021. Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach. In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.89"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3679009"},{"key":"e_1_3_2_1_8_1","volume-title":"Efficient Parallel and External Matching. In European Conference on Parallel Processing (Euro-Par) (Lecture Notes in Computer Science","volume":"670","author":"Birn Marcel","year":"2013","unstructured":"Marcel Birn, Vitaly Osipov, Peter Sanders, Christian Schulz, and Nodari Sitchinava. 2013. Efficient Parallel and External Matching. In European Conference on Parallel Processing (Euro-Par) (Lecture Notes in Computer Science, Vol. 8097). Springer, 659--670."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Guy Blelloch and Andrew Brady. 2025. Parallel Batch-Dynamic Maximal Matching with Constant Work per Update. (2025). arXiv:2503.09908","DOI":"10.1145\/3694906.3743313"},{"key":"e_1_3_2_1_10_1","unstructured":"Guy E. Blelloch. 1993. Prefix Sums and Their Applications. In Synthesis of Parallel Algorithms John Reif (Ed.). Morgan Kaufmann."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"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","volume-title":"Dynamic Matching Algorithms. Ph. D. Dissertation","author":"Burq Maximilien","unstructured":"Maximilien Burq. 2019. Dynamic Matching Algorithms. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_15_1","volume-title":"A taxonomy of problems with fast parallel algorithms. Inf. Control 64 (March","author":"Cook Stephen A.","year":"1985","unstructured":"Stephen A. Cook. 1985. A taxonomy of problems with fast parallel algorithms. Inf. Control 64 (March 1985). Issue 1-3."},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_3_2_1_17_1","volume-title":"International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"23","author":"Dhulipala Laxman","year":"2024","unstructured":"Laxman Dhulipala, Michael Dinitz, Jakub \u0141\u0105cki, and Slobodan Mitrovi\u0107. 2024. Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling. In International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 319). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 19:1--19:23."},{"key":"e_1_3_2_1_18_1","volume-title":"Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Dhulipala Laxman","year":"2020","unstructured":"Laxman Dhulipala, David Durfee, Janardhan Kulkarni, Richard Peng, Saurabh Sawlani, and Xiaorui Sun. 2020. Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_2_1_21_1","article-title":"Tight Analysis of Parallel Randomized Greedy MIS","volume":"16","author":"Fischer Manuela","year":"2019","unstructured":"Manuela Fischer and Andreas Noever. 2019. Tight Analysis of Parallel Randomized Greedy MIS. ACM Transactions on Algorithms (TALG) 16, 1, Article 6 (Dec. 2019).","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_2_1_22_1","volume-title":"Parallel Dynamic Maximal Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Ghaffari Mohsen","year":"2024","unstructured":"Mohsen Ghaffari and Anton Trygub. 2024. Parallel Dynamic Maximal Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185438"},{"key":"e_1_3_2_1_24_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Gu Yan","unstructured":"Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A Top-Down Parallel Semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_26_1","series-title":"SIAM J. on Computing 15","volume-title":"A simple parallel algorithm for the maximal independent set problem","author":"Luby Michael","year":"1986","unstructured":"Michael Luby. 1986. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing 15 (1986). Issue 4."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806753"},{"key":"e_1_3_2_1_29_1","volume-title":"Conference on Innovations in Theoretical Computer Science (ITCS)","author":"Roghani Mohammad","year":"2022","unstructured":"Mohammad Roghani, Amin Saberi, and David Wajc. 2022. Beating the folklore algorithm for dynamic matching. In Conference on Innovations in Theoretical Computer Science (ITCS) (Berkeley, CA, USA)."},{"key":"e_1_3_2_1_30_1","volume-title":"Fully Dynamic Maximal Matching in Constant Update Time. In IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Solomon Shay","year":"2016","unstructured":"Shay Solomon. 2016. Fully Dynamic Maximal Matching in Constant Update Time. In IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_31_1","volume-title":"Batch-Parallel Euler Tour Trees. Algorithm Engineering and Experiments (ALENEX)","author":"Tseng Thomas","year":"2019","unstructured":"Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. 2019. Batch-Parallel Euler Tour Trees. Algorithm Engineering and Experiments (ALENEX) (2019)."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384258"}],"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.3743313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:50Z","timestamp":1777922390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":33,"alternative-id":["10.1145\/3694906.3743313","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743313","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"}}]}}