Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Abstract
In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within \(\tilde O(m+n^{2-\epsilon})\) work and \(\tilde O(n^{1-\epsilon})\) depth for some positive \(\epsilon \lt 0\). In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Graph Theory and Algorithms
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 6011–6028
- Publication date
- 1 January 2026
- Language
- EN