SELF-STABILIZING VERTEX COVER IN ANONYMOUS NETWORKS WITH OPTIMAL APPROXIMATION RATIO

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, triangle(2), triangle log(3) n}) rounds and requires O (triangle) memory per node.