A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
DOI10.1145/3060294zbMATH Open1426.68291OpenAlexW2626058046MaRDI QIDQ4640294FDOQ4640294
Authors: Keren Censor-Hillel, Gregory Schwartzman, 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
Recommendations
- A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
- A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
- Approximated distributed minimum vertex cover algorithms for bounded degree graphs
- Tight bounds on the round complexity of the distributed maximum coverage problem
- Deterministically maintaining a \((2 + \epsilon)\)-approximate minimum vertex cover in \(O(1/\epsilon^2)\) amortized update time
- A \((2-\varepsilon)\)-approximation ratio for vertex cover problem on special graphs
- Nearly optimal distributed edge coloring in O(log log n) rounds
- scientific article; zbMATH DE number 1594511
- On the approximability of the vertex cover and related problems
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)
Cited In (24)
- Distributed weighted vertex cover via maximal matchings
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
- A simple local 3-approximation algorithm for vertex cover
- What cannot be computed locally!
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
- Approximated distributed minimum vertex cover algorithms for bounded degree graphs
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Minimum vertex cover, distributed decision-making, and communication complexity
- Improved distributed approximations for maximum independent set
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Parameterized distributed algorithms
- Optimal distributed covering algorithms
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Distributed set cover approximation: primal-dual with optimal locality
- Computing and Combinatorics
- Optimal distributed covering algorithms
- A time hierarchy theorem for the LOCAL model
- A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Adapting local sequential algorithms to the distributed setting
- A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
This page was built for publication: A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640294)
