High-Probability Parallel Transitive-Closure Algorithms

DOI10.1137/0220006zbMATH Open0716.68041OpenAlexW2075862701MaRDI QIDQ3204039FDOQ3204039

Authors: Jeffrey D. Ullman, Mihalis Yannakakis 

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

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

zbMATH Keywords

reachabilityparallel algorithmstransitive closureprobabilistic algorithmsbreadth- first-search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cited In (25)

• Title not available (Why is that?)
• Randomized parallel algorithms
• Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique
• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• 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
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

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)