A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric

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 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.
Type de document :
Rapport
[Research Report] RR-7146, INRIA. 2009, pp.41
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00440276
Contributeur : Benjamin Depardon <>
Soumis le : jeudi 10 décembre 2009 - 09:56:53
Dernière modification le : mardi 16 janvier 2018 - 15:34:32
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 10:35:45

Fichier

RR-7146.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00440276, version 1

Collections

Citation

Eddy Caron, Ajoy Datta, Benjamin Depardon, Lawrence Larmore. A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric. [Research Report] RR-7146, INRIA. 2009, pp.41. 〈inria-00440276〉

Partager

Métriques

Consultations de la notice

216

Téléchargements de fichiers

90