approximation of the maximum matching in $ O (^ 2n) $ moves. However, the complexity tightness was not proved. In this paper, we exhibit a sub-exponential execution of this matching algorithm.
Mann et al.[11] designed the first algorithm computing a maximal matching that is a 2/3- approximation of the maximum matching in 2^ O (n) moves. However, the complexity tightness was not proved. In this paper, we exhibit a sub-exponential execution of this matching algorithm: this algorithm can stabilize after at most Ω (2^{sqrt (n)} moves under the central daemon.