A fault-containing self-stabilizing ( 3 − 2 Δ + 1 ) -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 ( 3 − 2 Δ + 1 ) -approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair schedul...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2011-07, Vol.412 (33), p.4361-4371
Main Authors: Turau, Volker, Hauck, Bernd
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Anonymous networks
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Contamination
Exact sciences and technology
Faults
Graph theory
Logic and foundations
Mathematical logic, foundations, set theory
Mathematics
Miscellaneous
Networks
Recovery
Recursion theory
Sciences and techniques of general use
Self-stabilizing algorithms
Tasks
Theoretical computing
Trees
Vertex cover
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a ( 3 − 2 Δ + 1 ) -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 ( log n ) 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2010.11.010