A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds

DOI10.1145/3060294zbMath1426.68291OpenAlexW2626058046MaRDI QIDQ4640294

Gregory Schwartzman, Keren Censor-Hillel, Reuven Bar Yehuda

Publication date: 17 May 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3060294

zbMATH Keywords

graph algorithmsdistributed computingapproximation algorithmsvertex coverlocal ratio

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (6)

Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Optimal distributed covering algorithms ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Unnamed Item ⋮ Distributed set cover approximation: Primal-dual with optimal locality

This page was built for publication: A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds