{"ID":2897210,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.06334","arxiv_id":"2507.06334","title":"Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees","abstract":"We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our algorithm processes all these updates in $ \\text{poly}(\\log n)$ depth, using a worst-case work bound of $b\\cdot \\text{poly}(\\log n)$ where $b$ denotes the batch size. This means the batch gets processed in $\\tilde{O}(b/p)$ time, given $p$ processors, which is optimal up to logarithmic factors. Previously, an algorithm with similar guarantees was known by the celebrated work of Liu, Shi, Yu, Dhulipala, and Shun [SPAA'22], but with the caveat of the work bound, and thus the runtime, being only amortized.","short_abstract":"We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our algorithm processes all these updates in $ \\text{poly}(\\log n)$ depth, using a worst-case work bound of $b\\cdot \\text{poly}(\\log n)$ where $b...","url_abs":"https://arxiv.org/abs/2507.06334","url_pdf":"https://arxiv.org/pdf/2507.06334v1","authors":"[\"Mohsen Ghaffari\",\"Jaehyun Koo\"]","published":"2025-07-08T18:44:08Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}