Near-optimal massively parallel graph connectivity

DOI10.1109/FOCS.2019.00095MaRDI QIDQ6944139zbMATH OpenFDO

Authors Jakub Łącki, H. Esfandiari, Soheil Behnezhad, Vahab S. Mirrokni, Laxman Dhulipala

Publication date 12 August 2025

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

Mathematics Subject Classification ID

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

Cited in

(6)

• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Massively parallel computation in a heterogeneous regime
• Log-diameter MST verification and sensitivity in MPC
• Streaming graph algorithms in the massively parallel computation model
• Learning spanning forests optimally in weighted undirected graphs with CUT queries
• O(1)-Round MPC algorithms for multi-dimensional grid graph connectivity, Euclidean MST and DBSCAN

This page was built for publication: Near-optimal massively parallel graph connectivity

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