Nearly work-efficient parallel algorithm for digraph reachability

DOI10.1137/18M1197850MaRDI QIDQ5129233zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

randomized algorithmsshortcutsreachabilityparallel algorithmsgraph search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)

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

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 512931 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 2079397 (Why is no real title available?)
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• A unified approach to models of synchronous parallel machines
• High-Probability Parallel Transitive-Closure Algorithms
• Introduction to algorithms
• Parallel Merge Sort
• Parallelism in random access machines
• Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
• Powers of tensors and fast matrix multiplication
• Probabilistic recurrence relations
• The Parallel Evaluation of General Arithmetic Expressions
• Time Bounded Random Access Machines with Parallel Processing
• Time-work tradeoffs for parallel algorithms

Cited in

(5)

• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• A work-efficient distributed algorithm for reachability analysis
• Nearly work-efficient parallel algorithm for digraph reachability
• Race detection and reachability in nearly series-parallel DAGs
• Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

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)