Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

Václav Rozhoň, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Žužić

Type: Article

Publication Date: 2023-05-16

Citations: 3

DOI: https://doi.org/10.1145/3564246.3585235

Locations

arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances	2022	Václav Rozhoň Bernhard Haeupler Anders Martinsson Christoph Grunau Goran Žužić
+ PDF Chat	Massively Parallel Algorithms for Approximate Shortest Paths	2024	Michal Dory Shaked Matar
+	Distributed Approximate Distance Oracles.	2018	Michael Dinitz Yasamin Nazari
+	Massively Parallel Approximate Distance Sketches	2018	Michael Dinitz Yasamin Nazari
+ PDF Chat	Efficient construction of directed hopsets and parallel approximate shortest paths	2020	Nairen Cao Jeremy T. Fineman Katina Russell
+	$(1+ε)$-Approximate Shortest Paths in Dynamic Streams	2021	Michael Elkin Chhaya Trehan
+ PDF Chat	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization	2015	Monika Henzinger Sebastian Krinninger Danupon Nanongkai
+	$(1+\epsilon)$-Approximate Shortest Paths in Dynamic Streams	2021	Michael Elkin Chhaya Trehan
+	Fast 2-Approximate All-Pairs Shortest Paths	2023	Michal Dory Sebastian Förster Yael Kirkpatrick Yasamin Nazari Virginia Vassilevska Williams Tijn de Vos
+	Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths	2019	Nairen Cao Jeremy T. Fineman Katina Russell
+	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths	2016	Michael Elkin Ofer Neiman
+	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths	2016	Michael Elkin Ofer Neiman
+ PDF Chat	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization	2016	Monika Henzinger Sebastian Krinninger Danupon Nanongkai
+ PDF Chat	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths	2016	Michael Elkin Ofer Neiman
+	Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees	2015	Shiri Chechik Edith Cohen Haim Kaplan
+ PDF Chat	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths	2019	Michael Elkin Ofer Neiman
+	Faster Parallel Algorithm for Approximate Shortest Path	2019	Jason Li
+ PDF Chat	Parallel approximate undirected shortest paths via low hop emulators	2020	Alexandr Andoni Clifford Stein Peilin Zhong
+	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications	2022	Michael Elkin Bernhard Haeupler Václav Rozhoň Christoph Grunau
+ PDF Chat	A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths	2019	Monika Henzinger Sebastian Krinninger Danupon Nanongkai

Works That Cite This (1)

Action	Title	Year	Authors
+	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances	2023	Václav Rozhoň Bernhard Haeupler Anders Martinsson Christoph Grunau Goran Žužić

Works Cited by This (15)

Action	Title	Year	Authors
+ PDF Chat	Parallel graph decompositions using random shifts	2013	Gary L. Miller Richard Peng Shen Xu
+ PDF Chat	Approximate distance oracles with constant query time	2014	Shiri Chechik
+ PDF Chat	Distributed exact shortest paths in sublinear time	2017	Michael Elkin
+ PDF Chat	Thorup–Zwick emulators are universally optimal hopsets	2018	Shang-En Huang Seth Pettie
+	Nearly work-efficient parallel algorithm for digraph reachability	2018	Jeremy T. Fineman
+ PDF Chat	Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths	2019	Michael Elkin Ofer Neiman
+ PDF Chat	Efficient construction of directed hopsets and parallel approximate shortest paths	2020	Nairen Cao Jeremy T. Fineman Katina Russell
+	Faster parallel algorithm for approximate shortest path	2020	Jason Li
+ PDF Chat	Parallel approximate undirected shortest paths via low hop emulators	2020	Alexandr Andoni Clifford Stein Peilin Zhong
+ PDF Chat	A Faster Distributed Single-Source Shortest Paths Algorithm	2018	Sebastian Forster Danupon Nanongkai