STOC2022
Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms
Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li
22 citations
Abstract
This paper presents near-optimal deterministic parallel and distributed algorithms for computing (1+eps)-approximate single-source shortest paths in any undirected weighted graph.