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

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

zbMATH Keywords

random walkspectral gapsparse connectivity

Mathematics Subject Classification ID

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

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 that?)
• Title not available (Why is that?)

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)