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

Preprint · Elkin Michael, Matar Shaked

- Archive id: arxiv:2009.14729
- Published: 2020-09-30
- arXiv: https://arxiv.org/abs/2009.14729
- Source URL: https://arxiv.org/abs/2009.14729
- PDF: https://arxiv.org/pdf/2009.14729
- Provenance: arxiv

## Abstract

We study a $(1+ε)$-approximate single-source shortest paths (henceforth, $(1+ε)$-SSSP) in $n$-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A randomized algorithm with polylogarithmic time and slightly super-linear work $\\tilde{O}(\|E\|\\cdot n^ρ)$, for an arbitrarily small $ρ\>0$, was given by Cohen \[Coh94\] more than $25$ years ago. Exciting progress on this problem was achieved in recent years \[ElkinN17,ElkinN19,Li19,AndoniSZ19\], culminating in randomized polylogarithmic time and $\\tilde{O}(\|E\|)$ work. However, the question of whether there exists a deterministic counterpart of Cohen's algorithm remained wide open. In the current paper we devise the first deterministic polylogarithmic-time algorithm for this fundamental problem, with work $\\tilde{O}(\|E\|\\cdot n^ρ)$, for an arbitrarily small $ρ\>0$. This result is based on the first efficient deterministic parallel algorithm for building hopsets, which we devise in this paper.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.