The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

Autor: Johanne Cohen, Jonas Lefèvre, Khaled Maâmra, Laurence Pilard, George Manoussakis
Přispěvatelé: Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Parallélisme Réseaux Algorithmes Distribués (LI-PaRAD), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2019
Předmět:
Zdroj: Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2019, 782, pp.54-78. ⟨10.1016/j.tcs.2019.02.031⟩
ISSN: 0304-3975
1879-2294
DOI: 10.1016/j.tcs.2019.02.031
Popis: 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 × n 2 ) 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.
Databáze: OpenAIRE
Externí odkaz: