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

DOI10.1016/J.TCS.2010.11.010MaRDI QIDQ555319zbMATH OpenOpenAlexFDO

Authors 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

anonymous networksself-stabilizing algorithmsvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Self-stabilizing vertex cover in anonymous networks with optimal approximation ratio
• Approximation of Self-stabilizing Vertex Cover Less Than 2
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

Cites work

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

Cited in

(4)

• 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
• Self-stabilizing vertex cover in anonymous networks with optimal approximation ratio

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q555319)