Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Preprint
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-ε})$ work and $\tilde{O}(n^{1-ε})$ depth for some positive $ε>0$. In particular, for dense graphs with non-negative real weights, we provide the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Our result immediately yields improved strongly polynomial parallel algorithms for min-cost flow and the assignment problem. It also leads to the first non-trivial strongly polynomial dynamic algorithm for minimum mean cycle. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Integer priority queues with decrease key in constant time and the single source shortest paths problemJournal of Computer and System Sciences, 2004
- Time–Work Tradeoffs of the Single-Source Shortest Paths ProblemJournal of Algorithms, 1999
- A Randomized Parallel Algorithm for Single-Source Shortest PathsJournal of Algorithms, 1997
- Using Selective Path-Doubling for Parallel Shortest-Path ComputationsJournal of Algorithms, 1997
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arraysTheoretical Computer Science, 1991
- An improved parallel algorithm that computes the BFS numbering of a directed graphInformation Processing Letters, 1988
- A strongly polynomial minimum cost circulation algorithmCombinatorica, 1985
- A Regular Layout for Parallel AddersIEEE Transactions on Computers, 1982
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978
- Optimal Cycles in Graphs and the Minimal Cost-To-Time Ratio Problem1972