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.68032OpenAlexW1981311956MaRDI 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 coveranonymous networksself-stabilizing algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (3)

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

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

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