Distributed planar reachability in nearly optimal time
From MaRDI portal
Recommendations
- Decremental single-source reachability in planar digraphs
- Near-optimal distributed DFS in planar graphs
- Reachability and shortest paths in the broadcast CONGEST model
- Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
- Nearly work-efficient parallel algorithm for digraph reachability
Cites work
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- A Separator Theorem for Planar Graphs
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A distributed algorithm for directed minimum-weight spanning tree
- Compact oracles for reachability and approximate distances in planar digraphs
- Distance labeling in graphs (extended abstract)
- Distributed Computing: A Locality-Sensitive Approach
- Distributed algorithms for planar networks. I: Planar embedding
- Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
- Distributed approximation algorithms for weighted shortest paths
- Distributed verification and hardness of distributed approximation
- Distributed verification and hardness of distributed approximation
- Exact distance oracles for planar graphs
- Fast partial distance estimation and applications
- Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
- Improved distributed algorithms for exact shortest paths
- Low-congestion shortcuts without embedding
- Minor excluded network families admit fast distributed algorithms
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Near-optimal compression for the planar graph metric
- Near-optimal distributed DFS in planar graphs
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- New hardness results for planar graph problems in p and an algorithm for sparsest cut
- Planar diameter via metric compression
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Reachability and shortest paths in the broadcast CONGEST model
- Round- and message-optimal distributed graph algorithms
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
Cited in
(2)
This page was built for publication: Distributed planar reachability in nearly optimal time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535037)
