---

A New Self-stabilizing Algorithm for Maximal 2-packing

Year: 2010 Volume: 4 Issue: 3 424 - 427 Pages

• Authors:
• Zhengnan Shi

Abstract: In the self-stabilizing algorithmic paradigm, each node has a local view of the system, in a finite amount of time the system converges to a global state with desired property. In a graph G = (V, E), a subset S C V is a 2-packing if Vi c V: IN[i] n SI

• Keywords:
• self-stabilization
• 2-packing
• distributed computing
• fault tolerance
• graph algorithms

A Self-stabilizing Algorithm for Maximum Popular Matching of Strictly Ordered Preference Lists

Year: 2009 Volume: 3 Issue: 11 1058 - 1067 Pages

• Authors:
• Zhengnan Shi

Abstract: In this paper, we consider the problem of Popular Matching of strictly ordered preference lists. A Popular Matching is not guaranteed to exist in any network. We propose an IDbased, constant space, self-stabilizing algorithm that converges to a Maximum Popular Matching an optimum solution, if one exist. We show that the algorithm stabilizes in O(n5) moves under any scheduler (daemon).

• Keywords:
• self-stabilization
• popular matching
• algorithm
• distributed computing
• fault tolerance