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

DOI10.1145/3293611.3331596OpenAlexW2963629655MaRDI QIDQ5145258FDOQ5145258

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)

Cited In (8)

• 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
• Deterministic Massively Parallel Connectivity
• Time-optimal construction of overlay networks
• 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)