Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
In this talk, 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 …