2015 | OriginalPaper | Buchkapitel
An Efficient Silent Self-Stabilizing Algorithm for 1-Maximal Matching in Anonymous Networks
Erschienen in:
WALCOM: Algorithms and Computation
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.
