Parallel graph connectivity in log diameter rounds

DOI10.1109/FOCS.2018.00070MaRDI QIDQ6944342zbMATH OpenFDO

Authors Alexandr Andoni, Peilin Zhong, Clifford Stein, Zhao Song, Zhengyu Wang

Publication date 12 August 2025

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

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(7)

• Massively parallel approximate Steiner tree algorithms
• 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
• Parallel derandomization for coloring
• O(1)-Round MPC algorithms for multi-dimensional grid graph connectivity, Euclidean MST and DBSCAN

This page was built for publication: Parallel graph connectivity in log diameter rounds

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