2016/04/27 by Cohen, Johanne, Lefèvre, Jonas, Maâmra, Khaled +2
#C.2.1 #Distributed #F.2 #F.2.1 #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1604.08066
Manne et al. designed the first algorithm computing a maximal matching that is a 2/3 -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.