A simple local 3-approximation algorithm for vertex cover
arXiv:0810.2175 · doi:10.1016/j.ipl.2009.02.017
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