Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00384
An Efficient Silent SelfStabilizing 1Maximal Matching Algorithm in Anonymous Networks
Vol. 20, no. 1, pp. 5978, 2016. Regular paper.
Abstract We propose a new selfstabilizing 1maximal matching algorithm which is silent and works for any anonymous networks without a cycle of length of a multiple of 3 under a central unfair daemon. The 1maximal matching is a 2/3approximation to the maximum matching, and expected to get more matching pairs than a maximal matching, which only guarantees a 1/2approximation. The time complexity of the proposed algorithm is O(e) moves, which is O(n) moves if we restrict the topology to trees or rings whose length is not a multiple of 3, where n and e be the numbers of nodes and edges in a graph, respectively. The best existing result for 1maximal matching for anonymous networks is an algorithm of Goddard et al. which works for anonymous trees and anonymous rings whose length is not a multiple of 3 under a central daemon, and the time complexity is O(n^{4}) moves. Therefore, the result in this paper is a significant improvement from the best existing results.

Submitted: March 2015.
Reviewed: August 2015.
Revised: August 2015.
Accepted: September 2015.
Final: January 2016.
Published: February 2016.
