3 papers
cs.DC2016
Polynomial self-stabilizing algorithm and proof for a 2/3-approximation of a maximum matching
Johanne Cohen, Khaled Maâmra, George Manoussakis +1
We present the first polynomial self-stabilizing algorithm for finding a -approximation of a maximum matching in a general graph. The previous best known algorithm has bee…
cs.DC2016
Self-Stabilizing Maximal Matching and Anonymous Networks
Johanne Cohen, Jonas Lefèvre, Khaled Maâmra +2
We propose a self-stabilizing algorithm for computing a maximal matching in an anonymous network. The complexity is moves with high probability, under the adversarial dist…
cs.DC2016
The Manne et al. self-stabilizing 2/3-approximation matching algorithm is sub-exponential
Johanne Cohen, Jonas Lefèvre, Khaled Maâmra +2
Manne et al. designed the first algorithm computing a maximal matching that is a 2/3 -approximation of the maximum matching in moves. However, the complexity tightness was…