Parallel reachability in almost linear work and square root depth

DOI10.1109/FOCS.2019.00098MaRDI QIDQ6944136zbMATH OpenFDO

Authors Arun Jambulapati, Aaron Sidford, Yang P. Liu

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2019.00098

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(5)

• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• An evaluation of massively parallel algorithms for DFA minimization
• Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights
• Giving some slack: shortcuts and transitive closure compressions
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Parallel reachability in almost linear work and square root depth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6944136)