A Self-Stabilizing K-clustering algorithm for weighted graphs

Résumé : Les réseaux mobiles ad hoc ainsi que les plate-formes de grille sont des environements distribués et sujets à de nombreuses erreurs. Les coûts de communication au sein de ses infrastructures peuvent être améliorés, ou tout au moins bornés par l'utilisation d'un k-regroupement. Un k-regroupement d'un graphe, est une partition des noeuds en ensembles disjoints, nommés grappes ou clusters, dans lesquels chaque noeud est à une distance au plus k d'un noeud élu au sein du cluster, appelé clusterhead. Nous présentons un algorithme asynchrone, distribué et auto-stabilisant pour construire un ensemble k-regroupement d'un réseau de noeuds ayant des identifiants uniques, et connectés par des arêtes pondérées. L'algorithme se base sur les comparaisons des identifiants, il s'exécute en O(nk), et requiert O(log n + log k) d'espace mémoire par processus, où n est la taille du réseau. Nous présentons la première solution au problème du k-regroupement sur des graphes pondérés.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2010, 70 (11), pp.1159-1173
Liste complète des métadonnées

https://hal.inria.fr/hal-00758590
Contributeur : Eddy Caron <>
Soumis le : jeudi 29 novembre 2012 - 01:56:47
Dernière modification le : vendredi 20 avril 2018 - 15:44:24

Identifiants

  • HAL Id : hal-00758590, version 1

Collections

Citation

Eddy Caron, Ajoy Datta, Benjamin Depardon, Lawrence Larmore. A Self-Stabilizing K-clustering algorithm for weighted graphs. Journal of Parallel and Distributed Computing, Elsevier, 2010, 70 (11), pp.1159-1173. 〈hal-00758590〉

Partager

Métriques

Consultations de la notice

141