{"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":1777954606740,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":38,"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.3743328","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"225-239","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees"],"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","volume-title":"Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in neural information processing systems, 18","author":"Alvarez-Hamelin J","year":"2005","unstructured":"[AHDBV05] J Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, and Alessandro Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. Advances in neural information processing systems, 18, 2005."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_34"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461785"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_1_10_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_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.110"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-020-69464-3"},{"key":"e_1_3_2_1_13_1","first-page":"685","volume-title":"Finding the best k in core decomposition: A time and space optimal solution. In 2020 IEEE 36th International Conference on Data Engineering (ICDE)","author":"Chu Deming","year":"2020","unstructured":"[CZL+20] Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. Finding the best k in core decomposition: A time and space optimal solution. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 685--696. IEEE, 2020. [DBS17] Laxman Dhulipala, Guy Blelloch, and Julian Shun. Julienne: A framework for parallel graph algorithms using work-efficient bucketing. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 293--304, 2017."},{"key":"e_1_3_2_1_14_1","volume-title":"Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing (TOPC), 8(1):1--70","author":"Dhulipala Laxman","year":"2021","unstructured":"[DBS21] Laxman Dhulipala, Guy E Blelloch, and Julian Shun. Theoretically efficient parallel graph algorithms can be fast and scalable. ACM Transactions on Parallel Computing (TOPC), 8(1):1--70, 2021."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.10"},{"key":"e_1_3_2_1_16_1","first-page":"1397","volume-title":"international conference on machine learning","author":"Esfandiari Hossein","year":"2018","unstructured":"[ELM18] Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. Parallel and streaming algorithms for k-core decomposition. In international conference on machine learning, pages 1397--1406. PMLR, 2018."},{"key":"e_1_3_2_1_17_1","first-page":"325","volume-title":"22nd International Conference on Extending Database Technology, EDBT 2019","author":"Esfahani Fatemeh","year":"2019","unstructured":"[ESTW19] Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. Efficient computation of probabilistic core decomposition at web-scale. In 22nd International Conference on Extending Database Technology, EDBT 2019, pages 325--336. OpenProceedings. org, 2019."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591094"},{"key":"e_1_3_2_1_19_1","first-page":"2201","volume-title":"International Conference on Machine Learning","author":"Ghaffari Mohsen","year":"2019","unstructured":"[GLM19] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovi\u0107. Improved parallel algorithms for density-based network clustering. In International Conference on Machine Learning, pages 2201--2210. PMLR, 2019."},{"key":"e_1_3_2_1_20_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_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659982"},{"key":"e_1_3_2_1_22_1","volume-title":"Explicit and implicit dynamic coloring of graphs with bounded arboricity. arXiv preprint arXiv:2002.10142","author":"Henzinger Monika","year":"2020","unstructured":"[HNW20] Monika Henzinger, Stefan Neumann, and Andreas Wiese. Explicit and implicit dynamic coloring of graphs with bounded arboricity. arXiv preprint arXiv:2002.10142, 2020."},{"key":"e_1_3_2_1_23_1","volume-title":"Parallel small vertex connectivity in near-linear work and polylogarithmic depth. arXiv preprint arXiv:2504.06033","author":"Jiang Yonggang","year":"2025","unstructured":"[ JY25] Yonggang Jiang and Changki Yun. Parallel small vertex connectivity in near-linear work and polylogarithmic depth. arXiv preprint arXiv:2504.06033, 2025."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1746"},{"key":"e_1_3_2_1_26_1","first-page":"532","volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II 41","author":"Kopelowitz Tsvi","year":"2014","unstructured":"[KKPS14] Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II 41, pages 532--543. Springer, 2014."},{"key":"e_1_3_2_1_27_1","first-page":"1482","volume-title":"Parallel k-core decomposition on multicore platforms. In 2017 IEEE international parallel and distributed processing symposium workshops (IPDPSW)","author":"Kabir Humayun","year":"2017","unstructured":"[KM17] Humayun Kabir and Kamesh Madduri. Parallel k-core decomposition on multicore platforms. In 2017 IEEE international parallel and distributed processing symposium workshops (IPDPSW), pages 1482--1491. IEEE, 2017."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep09602"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the VLDB Endowment","author":"Li Conggai","year":"2020","unstructured":"[LZZ+20] Conggai Li, Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Efficient progressive minimum k-core search. Proceedings of the VLDB Endowment, 2020."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3399028"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep19307"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00287-5"},{"key":"e_1_3_2_1_36_1","volume-title":"T-H Hubert Chan, and Mauro Sozio. Fully dynamic approximate k-core decomposition in hypergraphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(4):1--21","author":"Sun Bintao","year":"2020","unstructured":"[SCS20] Bintao Sun, T-H Hubert Chan, and Mauro Sozio. Fully dynamic approximate k-core decomposition in hypergraphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(4):1--21, 2020."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538584"}],"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.3743328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:18:56Z","timestamp":1777922336000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":38,"alternative-id":["10.1145\/3694906.3743328","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743328","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"}}]}}