یک الگوریتم خوشه بندی KK خود تثبیت برای نمودار های وزن دار ☆
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|79159||2010||15 صفحه PDF||سفارش دهید||15546 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Journal of Parallel and Distributed Computing, Volume 70, Issue 11, November 2010, Pages 1159–1173
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 kk-clustering . A kk-clustering of a graph, is a partition of the nodes into disjoint sets, called clusters, in which every node is distance at most kk from a designated node in its cluster, called the clusterhead . A self-stabilizing asynchronous distributed algorithm is given for constructing a kk-clustering of a connected network of processes with unique IDs and weighted edges. The algorithm is comparison based, takes O(nk)O(nk) time, and uses O(logn+logk)O(logn+logk) space per process, where nn is the size of the network. To the best of our knowledge, this is the first solution to the kk-clustering problem on weighted graphs.