ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 30/10 - 2011  - pp.1191-1216  - doi:10.3166/tsi.30.1191-1216
TITRE
Un algorithme autostabilisant pour le problème du K-partitionnement sur graphe pondéré

TITLE
A self-stabilizing algorithm for the K-clustering problem on weighted graphs

RÉSUMÉ

Les réseaux mobiles ad hoc ainsi que les plates-formes de grille sont des environnements distribués et sujets à de nombreuses erreurs. Les coûts de communication au sein de ces 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 de nœuds en ensembles disjoints, nommés grappes ou clusters, dans lesquels chaque noeud est à une distance au plus k d’un nœud élu au sein de la grappe, appelé clusterhead. Nous présentons un algorithme asynchrone, distribué et autostabilisant pour construire un 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 des comparaisons entre les 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. À notre connaissance, c’est la première solution distribuée au problème du k-regroupement sur des graphes pondérés.



ABSTRACT

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 at a 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. To the best of our knowledge, this is the first distributed solution to the k-clustering problem on weighted graphs.



AUTEUR(S)
Eddy CARON, Ajoy K. DATTA, Benjamin DEPARDON, Lawrence L. LARMORE

MOTS-CLÉS
K-partitionnement, autostabilisation, graphe pondéré.

KEYWORDS
K-clustering, self-stabilization, weighted graph.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (389 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier