A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

Abstract: The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a -approximation of the optimal solution. They established that their algorithm stabilizes after (resp. ) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after moves under the central scheduler and that a modified version of the algorithm also stabilizes after moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms. [Copyright &y& Elsevier]