Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

DOI10.1145/3212734.3212743zbMath1428.68376arXiv1802.08237OpenAlexW2788015272MaRDI QIDQ5197674

Ronitt Rubinfeld, Christian Konrad, Themis Gouleakis, Mohsen Ghaffari, Slobodan Mitrović

Publication date: 19 September 2019

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

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

zbMATH Keywords

maximum matchingvertex covermaximal independent setmassively parallel computationcongested clique

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

Equivalence classes and conditional hardness in massively parallel computations, Deterministic Massively Parallel Connectivity, Time-optimal construction of overlay networks, Component stability in low-space massively parallel computation, Distributed Symmetry Breaking on Power Graphs via Sparsification, Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory, Round Compression for Parallel Matching Algorithms, A simple augmentation method for matchings with applications to streaming algorithms, Unnamed Item, Unnamed Item, The Impact of Locality in the Broadcast Congested Clique Model, Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds, When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time, Congested Clique Algorithms for Graph Spanners, Fast approximate shortest paths in the congested clique, Distributed algorithms for matching in hypergraphs, Near-optimal scheduling in the congested clique