An Efficient Silent Self-Stabilizing Algorithm for 1-Maximal Matching in Anonymous Networks

摘要

We propose a new self-stabilizing 1-maximal matching algorithm which is silent and works for any anonymous networks without a cycle of a length of a multiple of 3 under a central unfair daemon. Let n and e be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is O(e) moves. Therefore, the complexity is O(n) moves for trees or rings whose length is not a multiple of 3. That is a significant improvement from the best existing results of O(n~4) moves for the same problem setting.