Optimal distributed covering algorithms

DOI10.1007/s00446-021-00391-wOpenAlexW3154370415MaRDI QIDQ2689837

Gregory Schwartzman, Guy Even, Ken-ichi Kawarabayashi, Ran Ben-Basat

Publication date: 14 March 2023

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-021-00391-w

zbMATH Keywords

approximation algorithmsdistributed algorithmsvertex coverset cover

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Distributed algorithms for covering, packing and maximum weighted matching
• A simple local 3-approximation algorithm for vertex cover
• A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
• Local Computation
• The price of being near-sighted
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Deterministic coin tossing with applications to optimal parallel list ranking
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• Distributed weighted vertex cover via maximal matchings
• Reducibility among Combinatorial Problems
• Distributed set cover approximation: Primal-dual with optimal locality
• Some simple distributed algorithms for sparse networks
• Brief Announcement
• Distributed Approximation of Maximum Independent Set and Maximum Matching