Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs

DOI10.1145/3293611.3331596OpenAlexW2963629655MaRDI QIDQ5145258FDOQ5145258

Authors Sepehr Assadi, Xiaorui Sun, O. Weinstein 

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

random walkspectral gapsparse connectivity

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Log diameter rounds algorithms for 2-vertex and 2-edge connectivity
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory

Cited In (6)

• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Distributed-prover interactive proofs
• Equivalence classes and conditional hardness in massively parallel computations
• Maliciously secure massively parallel computation for all-but-one corruptions
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)

This page was built for publication: Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs

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