The Mann et al. self-stabilizing 2/3−approximation matching algorithm is sub-exponential.

Johanne Cohen (1) , Khaled Maâmra (2) , Laurence Pilard (2) , George Manoussakis

1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
2 UVSQ - Université de Versailles Saint-Quentin-en-Yvelines

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.

Mots clés: Approximation algorithm; Maximal Matching; Self-Stabilization

Domaines: Informatique

Johanne Cohen, Khaled Maâmra, Laurence Pilard, George Manoussakis. The Mann et al. self-stabilizing 2/3−approximation matching algorithm is sub-exponential.. [Research Report] Université de ParisSud. 2016. ⟨hal-01307886⟩