The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

摘要

We present the first polynomial self-stabilizing algorithm for finding a 1-maximal matching in a general graph. The previous best known algorithm has been presented by Manne et al. [20] and we show in this paper it has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a complexity in O(m x n(2)) moves, with n is the number of nodes and m is the number of edges. This is the first self stabilizing algorithm that solve this problem with a polynomial complexity. Moreover, our algorithm only needs one more boolean variable than the previous one. (C) 2019 Elsevier B.V. All rights reserved.