A simple local 3-approximation algorithm for vertex cover
published by Jukka Suomela
in 2008
in Informatics Engineering
and research's language is
English
Download
Abstract in English
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.