Nearly work-efficient parallel algorithm for digraph reachability

DOI10.1145/3188745.3188926zbMath1428.68360arXiv1711.01700OpenAlexW2964070308MaRDI QIDQ5230310

Jeremy T. Fineman

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.01700

zbMATH Keywords

shortcutsreachabilityrandomized algorithmparallel algorithmgraph 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)

Related Items (2)

Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Unnamed Item

This page was built for publication: Nearly work-efficient parallel algorithm for digraph reachability