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

作者：Turau Volker^*; Hauck Bernd

来源：Theoretical Computer Science, 2011, 412(40): 5527-5540.

DOI：10.1016/j.tcs.2010.11.032

• Self-stabilizing algorithms
• Approximation algorithms
• Weighted matching
• Distributed algorithms

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 2-approximation of the optimal solution. They established that their algorithm stabilizes after 0(2(n)) (resp. 0(3")) 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 0(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after 0(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.

• 出版日期2011-9-16