Self-stabilizing algorithm for maximum matching in trees.

S Ghosh, A Gupta, MH Karaata, SV Pemmaraju, TR94-08:

Postscript Document.


Abstract

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 distributed, {\em self-stabilizing} algorithm for finding a maximum matching in trees. Since our algorithm is self-stabilizing, it does not require any initialization and is tolerant to transient faults. The algorithm can also dynamically adapt to arbitrary changes in the topology of the tree.