Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth

Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1

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…