HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric (Revised Version of RR2008-31)

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

Contributor : Benjamin Depardon Connect in order to contact the contributor
Submitted on : Thursday, December 10, 2009 - 9:59:01 AM
Last modification on : Saturday, September 11, 2021 - 3:17:04 AM
Long-term archiving on: : Thursday, October 18, 2012 - 10:35:38 AM


Files produced by the author(s)


  • HAL Id : ensl-00440266, version 1



Eddy Caron, Ajoy Datta, Benjamin Depardon, Lawrence Larmore. A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric (Revised Version of RR2008-31). 2009. ⟨ensl-00440266⟩



Record views


Files downloads