SELF-STABILIZING VERTEX COVER IN ANONYMOUS NETWORKS WITH OPTIMAL APPROXIMATION RATIO
Volker Turau · Parallel Processing Letters · 2010
This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O( min {n, Δ2, Δ log 3 n}) rounds and requires O(Δ) memory per node.