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
2022年份
22被引次数
12顶会引用
摘要
This paper presents near-optimal deterministic parallel and distributed algorithms for computing (1+eps)-approximate single-source shortest paths in any undirected weighted graph.
问问这篇 Paper
问问你的智能体。
Lune 读过与它相关的顶会 Paper，每个回答都会注明依据哪几篇。
引用它的顶会 Paper12
- Universal Optimality of Dijkstra Via Beyond-Worst-Case HeapsBernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan 等FOCS 2024 · 被引用 33 次
- Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic DepthArpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil 等SODA 2024 · 被引用 7 次
- Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel ApplicationsVáclav Rozhon, Michael Elkin, Christoph Grunau, Bernhard HaeuplerFOCS 2022 · 被引用 5 次
- Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise IndependenceMohsen Ghaffari, Christoph Grunau, Václav RozhonFOCS 2023 · 被引用 3 次
- A Distributed Palette Sparsification TheoremMaxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn 等SODA 2024 · 被引用 3 次
相关 Paper
- Deterministic Padded Decompositions and Negative-Weight Shortest PathsJason LiSTOC 2026 · 被引用 6 次
- 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 等STOC 2023 · 被引用 6 次
- Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear TimeAaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol SaranurakFOCS 2021 · 被引用 27 次
- Parallel Exact Shortest Paths in Almost Linear Work and Square Root DepthNairen Cao, Jeremy T. FinemanSODA 2023 · 被引用 4 次
