We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
SELF-STABILIZING VERTEX COVER IN ANONYMOUS NETWORKS WITH OPTIMAL APPROXIMATION RATIO.
- Authors
TURAU, VOLKER
- Abstract
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.
- Subjects
SELF-stabilization (Computer science); COMPUTER algorithms; DISTRIBUTED algorithms; PARALLEL algorithms; COMPUTER networks
- Publication
Parallel Processing Letters, 2010, Vol 20, Issue 2, p173
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626410000132