Massively Parallel Computation of Matching and MIS in Sparse Graphs

DOI10.1145/3293611.3331609OpenAlexW2963813153MaRDI QIDQ5145260

Sebastian F. Brandt, Jara Uitto, Mahsa Derakhshan, Soheil Behnezhad, Manuela Fischer, Richard M. Karp, Mohammad Taghi Hajiaghayi

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://doi.org/10.1145/3293611.3331609

zbMATH Keywords

matchingapproximation algorithmssparse graphsarboricitymaximal independent setmassively parallel computationsublinear memory

Mathematics Subject Classification ID

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

Related Items (6)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Deterministic Massively Parallel Connectivity ⋮ Time-optimal construction of overlay networks ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ Unnamed Item

This page was built for publication: Massively Parallel Computation of Matching and MIS in Sparse Graphs