Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work

Elkin Michael, Matar Shaked

We study a $(1+\epsilon )$-approximate single-source shortest paths (henceforth, $(1+\epsilon )$-SSSP) in $n$-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A rand…