Distributed planar reachability in nearly optimal time
From MaRDI portal
Publication:6535037
DOI10.4230/lipics.disc.2020.38zbMATH Open1540.68196MaRDI QIDQ6535037
Publication date: 2 November 2023
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near-optimal low-congestion shortcuts on bounded parameter graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Fast Partial Distance Estimation and Applications
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- A Separator Theorem for Planar Graphs
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Distributed Verification and Hardness of Distributed Approximation
- Distributed exact shortest paths in sublinear time
- A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
- New hardness results for planar graph problems in p and an algorithm for sparsest cut
- Round- and Message-Optimal Distributed Graph Algorithms
- Minor Excluded Network Families Admit Fast Distributed Algorithms
- Planar diameter via metric compression
- Improved distributed algorithms for exact shortest paths
- Distributed approximation algorithms for weighted shortest paths
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Distributed Algorithms for Planar Networks I
- Low-Congestion Shortcuts without Embedding
- Improved algorithms for min cut and max flow in undirected planar graphs
- Distributed verification and hardness of distributed approximation
- Compact oracles for reachability and approximate distances in planar digraphs
- Near-optimal distributed DFS in planar graphs
- Reachability and shortest paths in the broadcast CONGEST model
- A distributed algorithm for directed minimum-weight spanning tree
Related Items (1)
This page was built for publication: Distributed planar reachability in nearly optimal time
