Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
From MaRDI portal
Publication:5197674
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
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
