Round compression for parallel matching algorithms

DOI10.1145/3188745.3188764zbMath1427.68354arXiv1707.03478OpenAlexW2734687249MaRDI QIDQ5230311

Piotr Sankowski, Krzysztof Onak, Slobodan Mitrović, Aleksander Mądry, Jakub Łącki, Artur Czumaj

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

maximum matchingvertex partitioninground compression

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (7)

Deterministic Massively Parallel Connectivity ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ Unnamed Item ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Distributed algorithms for matching in hypergraphs

This page was built for publication: Round compression for parallel matching algorithms