Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
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_ | 1866911649165737984 |
|---|---|
| author | Ashvinkumar, Vikrant Bernstein, Aaron Gutenberg, Maximilian Probst Saranurak, Thatchaphol |
| author_facet | Ashvinkumar, Vikrant Bernstein, Aaron Gutenberg, Maximilian Probst Saranurak, Thatchaphol |
| contents | We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=Ω(n^{2})$, our reachability and shortest path algorithms have depth only $n^{0.136}$ and $n^{0.25+o(1)}$, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems require $Ω(\sqrt{n})$ depth in all density regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03892 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth Ashvinkumar, Vikrant Bernstein, Aaron Gutenberg, Maximilian Probst Saranurak, Thatchaphol Data Structures and Algorithms We present parallel algorithms for computing single-source reachability and shortest paths on directed $n$-vertex $m$-edge graphs using near-linear $\tilde{O}(m)$ work and $o(\sqrt{n})$ depth whenever $m\ge n^{1+o(1)}$. At the extreme of $m=Ω(n^{2})$, our reachability and shortest path algorithms have depth only $n^{0.136}$ and $n^{0.25+o(1)}$, respectively. The state-of-the-art parallel algorithms with near-linear work for both problems require $Ω(\sqrt{n})$ depth in all density regimes. |
| title | Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.03892 |