A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks

DOI10.1016/j.tcs.2010.11.010zbMath1217.68032MaRDI QIDQ555319

Volker Turau, Bernd Hauck

Publication date: 22 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.010

zbMATH Keywords

vertex cover; anonymous networks; self-stabilizing algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68M14: Distributed systems

68W25: Approximation algorithms

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

Monotonic self-stabilization and its application to robust and adaptive pattern formation, Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains, Self-Stabilizing Domination Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems
• A simple local 3-approximation algorithm for vertex cover
• A new self-stabilizing maximal matching algorithm
• A self-stabilizing algorithm for maximal matching
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Fault-containing self-stabilizing distributed protocols
• An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• A SELF-STABILIZING DISTRIBUTED ALGORITHM TO FIND THE CENTER OF A TREE GRAPH
• Complexity of network synchronization
• Some simple distributed algorithms for sparse networks
• Dynamic and self-stabilizing distributed matching
• Approximation of Self-stabilizing Vertex Cover Less Than 2
• Some optimal inapproximability results