The Designs and Analyses of Self-Stabilizing Algorithm for Maximal Weight Matching Problem on Complete Graphs

Author: Rue-Yi Chen,Shun-Shii Lin(Graduate Institute of Information and Computer Education, National Taiwan Normal University)

Vol.&No.：Vol. 45, No. 1&2
Date：October 2000
Pages：21-36
DOI：10.6301/JNTNU.2000.45.03

Abstract：

In 1974, Dijsktra defined a self-stabilizing system as a system which is guaranteed to arrive at a legitimate state in a finite number of steps regardless of its initial state. Since his introduction, self-stabilizing algorithms gained wide-spread research interest. The objectives of this research are to design and analyze self-stabilizing algorithms for maximal weight matching problem. Firstly, Hsu and Huang proved that the time complexity of their self-stabilizing algorithm for finding a maximal matching in distributed networks is O(n3), where n is the number of nodes in the graph. In 1994, Tel introduced a variant function to show that the time complexity of Hsu-Huang's algorithm is O(n2). In this paper, we design a self-stabilizing algorithm for maximal weight matching of the complete graph and prove its correctness. The maximal weight matching problem is defined not only to find the maximal matching of the complete graph, but also to let the total weight of the matching edges be maximal. We combine Hsu-Huang's maximal matching alogrithm and new swapping rules. This system possesses the properties of fault tolerance and self-stabilization and has a time complexity O(n2+nk), where k is the largest weight over all edges in the graph.

Keywords：self-stabilizing algorithm, fault tolerance, maximal matching problem, maximal weight matching problem

《Full Text》