Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917283778002944 |
|---|---|
| author | Blelloch, Guy Brady, Andrew Dhulipala, Laxman Fineman, Jeremy Gowda, Kishen Hutton, Chase |
| author_facet | Blelloch, Guy Brady, Andrew Dhulipala, Laxman Fineman, Jeremy Gowda, Kishen Hutton, Chase |
| contents | A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper we present faster parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph. All results herein achieve polylogarithmic depth, with high probability (whp); the focus of this paper is on minimizing the work, which varies across results.
Our first result is the first parallel batch-dynamic algorithm to maintain an asymptotically optimal orientation with asymptotically optimal expected work bounds, in an amortized sense, improving over the prior best work bounds of Liu et al.~[SPAA~'22] by a logarithmic factor.
Our second result is a $O(c \log n)$ orientation algorithm with expected worst-case $O(\sqrt{\log n})$ work per edge update, where $c$ is a known upper-bound on the arboricity of the graph. This matches the best-known sequential worst-case $O(c \log n)$ orientation algorithm given by Berglin and Brodal ~[Algorithmica~'18], albeit in expectation.
Our final result is a $O(c + \log n)$-orientation algorithm with $O(\log^2 n)$ expected worst-case work per edge update. This algorithm significantly improves upon the recent result of Ghaffari and Koo~[SPAA~'25], which maintains a $O(c)$-orientation with $O(\log^9 n)$ worst-case work per edge whp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17811 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation Blelloch, Guy Brady, Andrew Dhulipala, Laxman Fineman, Jeremy Gowda, Kishen Hutton, Chase Distributed, Parallel, and Cluster Computing Data Structures and Algorithms A low out-degree orientation directs each edge of an undirected graph with the goal of minimizing the maximum out-degree of a vertex. In the parallel batch-dynamic setting, one can insert or delete batches of edges, and the goal is to process the entire batch in parallel with work per edge similar to that of a single sequential update and with span (or depth) for the entire batch that is polylogarithmic. In this paper we present faster parallel batch-dynamic algorithms for maintaining a low out-degree orientation of an undirected graph. All results herein achieve polylogarithmic depth, with high probability (whp); the focus of this paper is on minimizing the work, which varies across results. Our first result is the first parallel batch-dynamic algorithm to maintain an asymptotically optimal orientation with asymptotically optimal expected work bounds, in an amortized sense, improving over the prior best work bounds of Liu et al.~[SPAA~'22] by a logarithmic factor. Our second result is a $O(c \log n)$ orientation algorithm with expected worst-case $O(\sqrt{\log n})$ work per edge update, where $c$ is a known upper-bound on the arboricity of the graph. This matches the best-known sequential worst-case $O(c \log n)$ orientation algorithm given by Berglin and Brodal ~[Algorithmica~'18], albeit in expectation. Our final result is a $O(c + \log n)$-orientation algorithm with $O(\log^2 n)$ expected worst-case work per edge update. This algorithm significantly improves upon the recent result of Ghaffari and Koo~[SPAA~'25], which maintains a $O(c)$-orientation with $O(\log^9 n)$ worst-case work per edge whp. |
| title | Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.17811 |