A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2 |
| |
Authors: | Volker Turau Bernd Hauck |
| |
Affiliation: | Hamburg University of Technology, Institute of Telematics, Schwarzenbergstrasse 95, D-21073 Hamburg, Germany |
| |
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 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2n) (resp. O(3n)) 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 O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(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. |
| |
Keywords: | Self-stabilizing algorithms Approximation algorithms Weighted matching Distributed algorithms |
本文献已被 ScienceDirect 等数据库收录! |