Nearly work-efficient parallel algorithm for digraph reachability
From MaRDI portal
Publication:5129233
DOI10.1137/18M1197850zbMATH Open1476.68303OpenAlexW3093924778MaRDI QIDQ5129233FDOQ5129233
Authors: Jeremy T. Fineman 
Publication date: 26 October 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1197850
Recommendations
- Nearly work-efficient parallel algorithm for digraph reachability
- On the parallel complexity of digraph reachability
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
- Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)
Cites Work
- Introduction to algorithms
- Powers of tensors and fast matrix multiplication
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel Merge Sort
- Parallelism in random access machines
- The Parallel Evaluation of General Arithmetic Expressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- High-Probability Parallel Transitive-Closure Algorithms
- A Randomized Parallel Algorithm for Single-Source Shortest Paths
- Probabilistic recurrence relations
- A unified approach to models of synchronous parallel machines
- Time Bounded Random Access Machines with Parallel Processing
- Title not available (Why is that?)
- Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
- Time-work tradeoffs for parallel algorithms
Cited In (5)
- Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
- Nearly work-efficient parallel algorithm for digraph reachability
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Race detection and reachability in nearly series-parallel DAGs
- A work-efficient distributed algorithm for reachability analysis
This page was built for publication: Nearly work-efficient parallel algorithm for digraph reachability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5129233)
