A distributed self-stabilizing algorithm for finding maximum matching

摘要

Constructing a maximum matching is an important problem in graph theory with applications to problems such as job assignment and task scheduling. Many efficient sequential and parallel algorithms exist for solving the problem. However, no distributed algorithms are known. In this paper, we present a distribut- ed, self-stabilizing algorithm for finding a maximum matching in trees. Since our algorithm is self-stabilizing, it does not require any initialization and is toler- ant to transient faults. The algorithm can also dynamically adapt to arbitrary changes in the topology of the tree.