High-Probability Parallel Transitive-Closure Algorithms
From MaRDI portal
Publication:3204039
DOI10.1137/0220006zbMath0716.68041OpenAlexW2075862701MaRDI QIDQ3204039
Mihalis Yannakakis, Jeffrey D. Ullman
Publication date: 1991
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220006
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items (18)
Thorup-Zwick emulators are universally optimal hopsets ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Size-estimation framework with applications to transitive closure and reachability ⋮ Adapting parallel algorithms to the W-stream model, with applications to graph problems ⋮ On dynamic shortest paths problems ⋮ Nearly Work-Efficient Parallel Algorithm for Digraph Reachability ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Redundancy in distributed proofs ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
This page was built for publication: High-Probability Parallel Transitive-Closure Algorithms
