Distributed Approximation of Maximum Independent Set and Maximum Matching

DOI10.1145/3087801.3087806zbMath1380.68416arXiv1708.00276OpenAlexW2738712979MaRDI QIDQ5368958

Keren Censor-Hillel, Mohsen Ghaffari, Gregory Schwartzman, Reuven Bar Yehuda

Publication date: 11 October 2017

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

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

Node and edge averaged complexities of local graph problems ⋮ Optimal distributed covering algorithms ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Unnamed Item ⋮ Simple and local independent set approximation ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Distributed set cover approximation: Primal-dual with optimal locality