A simple local 3-approximation algorithm for vertex cover

Abstract

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.

6 pages, 1 figure

References in corpus (2)

• Approximating max-min linear programs with local algorithms
• Tight local approximation results for max-min linear programs

Cited by in corpus (4)

• Pervasive AI for IoT applications: A Survey on Resource-efficient Distributed Artificial Intelligence
• Weak Models of Distributed Computing, with Connections to Modal Logic
• Distributed Vertex Cover Algorithms For Wireless Sensor Networks
• On distributed algorithms for minimum dominating set problem and beyond