A self-stabilizing algorithm to maximal 2-packing with improved complexity

DOI10.1016/j.ipl.2012.03.018zbMath1243.68089OpenAlexW2010380569MaRDI QIDQ436592

Zhengnan Shi

Publication date: 25 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.03.018

zbMATH Keywords

fault tolerancegraph algorithmsdistributed computingself-stabilization2-packing

Mathematics Subject Classification ID

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

Related Items

A fast approximation algorithm for the maximum 2-packing set problem on planar graphs ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ A genetic algorithm for the maximum 2-packing set problem ⋮ Self-Stabilizing Domination Algorithms ⋮ The probabilistic approach to limited packings in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Local stabilizer
• Distance-\(k\) knowledge in self-stabilizing algorithms
• A self-stabilizing algorithm for maximal matching
• Relations between packing and covering numbers of a tree
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
• A Best Possible Heuristic for the k-Center Problem
• Self-stabilizing systems in spite of distributed control
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS
• Introduction to Distributed Algorithms