A self-stabilizing -approximation algorithm for the maximum matching problem

Abstract: The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and the self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (-approximation) matching in a general graph, as well as computing a -approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a -approximation to the maximum matching problem in a general graph. We show that our new algorithm, when run under a distributed adversarial daemon, stabilizes after at most rounds. However, it might still use an exponential number of time steps. [Copyright &y& Elsevier]