Geodesic
An Efficient Silent Self-Stabilizing 1-Maximal Matching Algorithm in Anonymous Networks
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015) , Tome 20 (2016) no. 1, pp. 59-78.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We propose a new self-stabilizing 1-maximal matching algorithm which is silent and works for any anonymous networks without a cycle of length of a multiple of 3 under a central unfair daemon. The 1-maximal matching is a 2/3-approximation to the maximum matching, and expected to get more matching pairs than a maximal matching, which only guarantees a 1/2-approximation. The time complexity of the proposed algorithm is O(e) moves, which is O(n) moves if we restrict the topology to trees or rings whose length is not a multiple of 3, where n and e be the numbers of nodes and edges in a graph, respectively. The best existing result for 1-maximal matching for anonymous networks is an algorithm of Goddard et al. which works for anonymous trees and anonymous rings whose length is not a multiple of 3 under a central daemon, and the time complexity is O(n4) moves. Therefore, the result in this paper is a significant improvement from the best existing results.
DOI : 10.7155/jgaa.00384
Keywords: distributed algorithm, self-stabilization, graph theory, matching problem 
@article{JGAA_2016_20_1_a3,
     author = {Yuma Asada and Fukuhito Ooshita and Michiko Inoue},
     title = {An {Efficient} {Silent} {Self-Stabilizing} {1-Maximal} {Matching} {Algorithm} in {Anonymous} {Networks}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {59--78},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2016},
     doi = {10.7155/jgaa.00384},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00384/}
}
TY  - JOUR
AU  - Yuma Asada
AU  - Fukuhito Ooshita
AU  - Michiko Inoue
TI  - An Efficient Silent Self-Stabilizing 1-Maximal Matching Algorithm in Anonymous Networks
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 59
EP  - 78
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00384/
DO  - 10.7155/jgaa.00384
LA  - en
ID  - JGAA_2016_20_1_a3
ER  - 
%0 Journal Article
%A Yuma Asada
%A Fukuhito Ooshita
%A Michiko Inoue
%T An Efficient Silent Self-Stabilizing 1-Maximal Matching Algorithm in Anonymous Networks
%J Journal of Graph Algorithms and Applications
%D 2016
%P 59-78
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00384/
%R 10.7155/jgaa.00384
%G en
%F JGAA_2016_20_1_a3
Yuma Asada; Fukuhito Ooshita; Michiko Inoue. An Efficient Silent Self-Stabilizing 1-Maximal Matching Algorithm in Anonymous Networks. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation  (WALCOM 2015)
					, Tome 20 (2016) no. 1, pp. 59-78. doi : 10.7155/jgaa.00384. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00384/

Cité par Sources :