Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916833937850368 |
|---|---|
| author | Ghaffari, Mohsen Koo, Jaehyun |
| author_facet | Ghaffari, Mohsen Koo, Jaehyun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06334 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees Ghaffari, Mohsen Koo, Jaehyun Data Structures and Algorithms 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. |
| title | Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.06334 |