Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908441580142592 |
|---|---|
| author | Ghaffari, Mohsen Koo, Jaehyun |
| author_facet | Ghaffari, Mohsen Koo, Jaehyun |
| contents | This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an $n$-node undirected graph, in $\text{poly}(\log n)$ depth and using amortized work near-linear in the batch size. Our concrete results are as follows:
- Our base algorithm maintains a spanner with $(2k-1)$ stretch and $\tilde{O}(n^{1+1/k})$ edges, for any $k\geq 1$.
- Our first extension maintains a sparse spanner with only $O(n)$ edges, and $\tilde{O}(\log n)$ stretch.
- Our second extension maintains a $t$-bundle of spanners -- i.e., $t$ spanners, each of which is the spanner of the graph remaining after removing the previous ones -- and allows us to maintain cut/spectral sparsifiers with $\tilde{O}(n)$ edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06338 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parallel Batch-Dynamic Algorithms for Spanners, and Extensions Ghaffari, Mohsen Koo, Jaehyun Data Structures and Algorithms This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an $n$-node undirected graph, in $\text{poly}(\log n)$ depth and using amortized work near-linear in the batch size. Our concrete results are as follows: - Our base algorithm maintains a spanner with $(2k-1)$ stretch and $\tilde{O}(n^{1+1/k})$ edges, for any $k\geq 1$. - Our first extension maintains a sparse spanner with only $O(n)$ edges, and $\tilde{O}(\log n)$ stretch. - Our second extension maintains a $t$-bundle of spanners -- i.e., $t$ spanners, each of which is the spanner of the graph remaining after removing the previous ones -- and allows us to maintain cut/spectral sparsifiers with $\tilde{O}(n)$ edges. |
| title | Parallel Batch-Dynamic Algorithms for Spanners, and Extensions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.06338 |