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
2022Year
22Citations
12Top-tier 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.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Your agent calls
Lunesearch_papers
Free to start. No credit card required.
Terminal
Install the CLIlune papers get 149c1ef4-8bd7-4bfd-a7e9-74053fadb40cCited by top-tier papers12
- Universal Optimality of Dijkstra Via Beyond-Worst-Case HeapsBernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan et al.FOCS 2024 · 33 citations
- Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic DepthArpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil et al.SODA 2024 · 7 citations
- Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel ApplicationsVáclav Rozhon, Michael Elkin, Christoph Grunau, Bernhard HaeuplerFOCS 2022 · 5 citations
- Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise IndependenceMohsen Ghaffari, Christoph Grunau, Václav RozhonFOCS 2023 · 3 citations
- A Distributed Palette Sparsification TheoremMaxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn et al.SODA 2024 · 3 citations
Related papers
- Deterministic Padded Decompositions and Negative-Weight Shortest PathsJason LiSTOC 2026 · 6 citations
- Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSPAdam Karczmarz, Wojciech Nadara, Marek SokolowskiSODA 2026
- Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate DistancesVáclav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau et al.STOC 2023 · 6 citations
- Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear TimeAaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol SaranurakFOCS 2021 · 27 citations
- Parallel Exact Shortest Paths in Almost Linear Work and Square Root DepthNairen Cao, Jeremy T. FinemanSODA 2023 · 4 citations
