A fault-containing self-stabilizing -approximation algorithm for vertex cover in anonymous networks

The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a -approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair scheduler, stabilizes after O(n+m) moves respectively O(Δ) rounds, and requires O(logn) storage per node. Recovery from a single fault is reached within a constant time and the contamination number is O(Δ). For trees the algorithm computes a 2-approximation of a minimum vertex cover.