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 n...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-08, Vol.782, p.54-78
Main Authors: Cohen, Johanne, Lefèvre, Jonas, Maâmra, Khaled, Manoussakis, George, Pilard, Laurence
Format: Article
Language:English
Subjects:
1-maximal matching
[formula omitted]-approximation
Cognitive science
Computer science
Self-stabilization
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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×n2) 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.02.031