High-Probability Parallel Transitive-Closure Algorithms
From MaRDI portal
Publication:3204039
Recommendations
- An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
- Algorithms for dense graphs and networks on the random access computer
- Time-work tradeoffs for parallel algorithms
- scientific article; zbMATH DE number 934538
- Parallel Transitive Closure and Point Location in Planar Structures
Cited in
(25)- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- scientific article; zbMATH DE number 1948455 (Why is no real title available?)
- Randomized parallel algorithms
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Parallel algorithms for transitive reduction for weighted graphs
- Thorup-Zwick emulators are universally optimal hopsets
- Fully dynamic all pairs shortest paths with real edge weights
- Transitive compaction in parallel via branchings
- Redundancy in distributed proofs
- A hierarchy of lower bounds for sublinear additive spanners
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- Nearly work-efficient parallel algorithm for digraph reachability
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- On dynamic shortest paths problems
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
- Parallel Transitive Closure and Point Location in Planar Structures
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Size-estimation framework with applications to transitive closure and reachability
- Algorithmic techniques for maintaining shortest routes in dynamic networks
- Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
This page was built for publication: High-Probability Parallel Transitive-Closure Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204039)
