Fast Distributed Construction of Small k-Dominating Sets and Applications
Fast Distributed Construction of Small k-Dominating Sets and Applications
复制标题
小型 k 支配集的快速分布式构建及应用
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
S. Kutten;D. Peleg
本文介绍了一种快速分布式算法，以计算一个小型主体式的setD（对于任何固定克），并计算其诱导的图形分区（将图形分解为以dd的顶点为中心的radiuskclusters）。算法ISO（klog*n）的时间复杂性。 Smallk为主机的集合在许多领域都有应用程序，包括带有稀疏路由表的路由，分布式数据结构的设计以及分布式网络中的中心选择。本文描述的主要应用程序涉及一种快速分布的算法，用于构建最小重量跨越树（MST）。在直径的Ann-Vertex网络上，新算法在时间上构建了MST，从而改善了先前的结果。
This article presents a fast distributed algorithm to compute a smallk-dominating setD(for any fixedk) and to compute its induced graph partition (breaking the graph into radiuskclusters centered around the vertices ofD). The time complexity of the algorithm isO(klog*n). Smallk-dominating sets have applications in a number of areas, including routing with sparse routing tables, the design of distributed data structures, and center selection in a distributed network. The main application described in this article concerns a fast distributed algorithm for constructing a minimum-weight spanning tree (MST). On ann-vertex network of diameterd, the new algorithm constructs an MST in time, improving on previous results.