Undirected (1+ <i>𝜀</i> )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms
Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Žužić, Jason Li
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.
Topics & Concepts
Undirected graphComputer scienceMinor (academic)Distributed algorithmAlgorithmGraphShortest path problemCombinatoricsTheoretical computer scienceMathematicsDistributed computingPolitical scienceLawComplexity and Algorithms in GraphsStochastic Gradient Optimization TechniquesAdvanced Graph Theory Research