Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

DOI10.1137/18M1197850zbMath1476.68303OpenAlexW3093924778MaRDI QIDQ5129233

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

shortcutsreachabilityparallel algorithmsrandomized algorithmsgraph search

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• High-Probability Parallel Transitive-Closure Algorithms
• Powers of tensors and fast matrix multiplication
• Parallel Merge Sort
• Time Bounded Random Access Machines with Parallel Processing
• Probabilistic recurrence relations
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• Time-work tradeoffs for parallel algorithms
• The Parallel Evaluation of General Arithmetic Expressions
• Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
• A unified approach to models of synchronous parallel machines
• Parallelism in random access machines

This page was built for publication: Nearly Work-Efficient Parallel Algorithm for Digraph Reachability