2026.02.24, Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP скачать в хорошем качестве

2026.02.24, Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP February 24 Tuesday @ 4:30 PM - 5:30 PM KST Room B332, IBS (기초과학연구원) Marek Sokołowski Max Planck Institute of Informatics https://mnbvmar.github.io 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 can be solved within $\tilde{O}(m+n^{2-\varepsilon})$ work and $\tilde{O}(n^{1-\varepsilon})$ depth for some positive $\varepsilon＞0$. For dense graphs with non-negative real weights, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights. This is a joint work with Adam Karczmarz and Wojciech Nadara.