A Self-Stabilizing K-clustering algorithm for weighted graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Parallel and Distributed Computing Année : 2010

A Self-Stabilizing K-clustering algorithm for weighted graphs

Résumé

Mobile ad hoc networks as well as grid platforms are distributed, changing and error prone environments. Communication costs within such infrastructure can be improved, or at least bounded, by using k-clustering. A k-clustering of a graph, is a partition of the nodes into disjoint sets, called clusters, in which every node is distance at most k from a designated node in its cluster, called the clusterhead. A self-stabilizing asynchronous distributed algorithm is given for constructing a k-clustering of a connected network of processes with unique IDs and weighted edges. The algorithm is comparison-based, takes O(nk) time, and uses O(log n + log k) space per process, where n is the size of the network. This is the first distributed solution to the k-clustering problem on weighted graphs.
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.
Fichier non déposé

Dates et versions

hal-00758590 , version 1 (29-11-2012)

Identifiants

  • HAL Id : hal-00758590 , version 1

Citer

Eddy Caron, Ajoy K. Datta, Benjamin Depardon, Lawrence L. Larmore. A Self-Stabilizing K-clustering algorithm for weighted graphs. Journal of Parallel and Distributed Computing, 2010, 70 (11), pp.1159-1173. ⟨hal-00758590⟩
106 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More