Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

DOI10.1137/1.9781611975482.98zbMath1431.68143arXiv1711.03076OpenAlexW2767578875MaRDI QIDQ5236282

MohammadHossein Bateni, Sepehr Assadi, Aaron Bernstein, Clifford Stein, Vahab S. Mirrokni

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (11)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ 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 ⋮ Round Compression for Parallel Matching Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Distributed algorithms for matching in hypergraphs

This page was built for publication: Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs