Given an arbitrary network $G$ of {\ndes} with unique IDs and no designated leader,and given a $k$-dominating set $I\subseteq G$, we propose a silent self-stabilizing distributed algorithm that computes a subset $D$ of $I$ which is a minimal $k$-dominating set of $G$.Using $D$ as the set of cluster heads, a partition of $G$ into clusters, each of radius $k$, follows.The algorithm is comparison-based, requires $O(\log n)$space per {\nde}, converges in $O(n)$ rounds and $O(n^2)$ steps,where $n$ is the size of the network, and works under an unfair scheduler.
['Ajoy Kumar Datta', 'Stéphane Devismes', 'Lawrence L. Larmore']
A Self-Stabilizing O(n)-Round k-Clustering Algorithm