Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
From MaRDI portal
Publication:6499233
DOI10.1145/3564246.3585235MaRDI QIDQ6499233
Christoph Grunau, Anders Martinsson, Goran Zuzic, Václav Rozhoň, Bernhard Haeupler
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Thorup-Zwick emulators are universally optimal hopsets
- The geometry of graphs and some of its algorithmic applications
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Heuristic shortest path algorithms for transportation applications: state of the art
- High-Probability Parallel Transitive-Closure Algorithms
- Approximate distance oracles
- Spanners and emulators with sublinear distance errors
- Efficient Algorithms for Shortest Paths in Sparse Networks
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
- Distributed exact shortest paths in sublinear time
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Introduction to local certification
- Faster parallel algorithm for approximate shortest path
- Parallel approximate undirected shortest paths via low hop emulators
- Efficient construction of directed hopsets and parallel approximate shortest paths
- Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts
- Nearly work-efficient parallel algorithm for digraph reachability
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- Approximate distance oracles with constant query time
- Distributed verification and hardness of distributed approximation
- Single-Source Shortest Paths in the CONGEST Model with Improved Bound
- Faster shortest-path algorithms for planar graphs
- Universally-optimal distributed algorithms for known topologies
- Distributed algorithms for low stretch spanning trees
This page was built for publication: Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances