A self-stabilizing k-clustering algorithm for weighted graphs

Eddy Caron

doi:10.1016/j.jpdc.2010.06.009

Return

A self-stabilizing k-clustering algorithm for weighted graphs

2010-11-01

PRE

Eddy Caron

Benjamin Depardon *

DOI：10.1016/j.jpdc.2010.06.009

Original

Original request for help

Save

Abstract

En 中文

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. To the best of our knowledge, this is the first solution to the k-clustering problem on weighted graphs. (c) 2010 Elsevier Inc. All rights reserved.

Keywords:

k-clustering

Self-stabilization

Weighted graph

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.