 |
 |
 |
 |
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.
Cited literature [18 references]
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00440266
Contributor : Benjamin Depardon <>
Submitted on : Thursday, December 10, 2009 - 9:59:01 AM
Last modification on : Friday, June 25, 2021 - 3:40:03 PM
Long-term archiving on: : Thursday, October 18, 2012 - 10:35:38 AM
Contributor : Benjamin Depardon <>
Submitted on : Thursday, December 10, 2009 - 9:59:01 AM
Last modification on : Friday, June 25, 2021 - 3:40:03 PM
Long-term archiving on: : Thursday, October 18, 2012 - 10:35:38 AM
File
RRLIP2009-33.pdf
Files produced by the author(s)