A Self-Stabilizing K-clustering algorithm for weighted graphs

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 :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00758590
Contributor : Eddy Caron <>
Submitted on : Thursday, November 29, 2012 - 1:56:47 AM
Last modification on : Monday, August 12, 2019 - 12:16:02 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

192