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