A near-tight lower bound on the time complexity of distributed MST construction
A near-tight lower bound on the time complexity of distributed MST construction
复制标题
分布式 MST 构建时间复杂度的近紧下界
DOI：
10.1109/sffcs.1999.814597
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Vitaly Rubinovich
中科院分区：
文献类型：
--
作者：
D. Peleg;Vitaly Rubinovich
本文给出了在有界消息模型下，在直径D=/SPL Omega/(Logn)的n点网络中分布式构造最小权生成树所需时间的下界/SPL Omega/~(D+/SPL Radic/n)。这建立了该问题的现有时间效率分布式算法的渐近最优性，其复杂性为O(D+/SPL Radic/nlog*n)。
This paper presents a lower bound of /spl Omega/~(D+/spl radic/n) on the time required for the distributed construction of a minimum-weight spanning tree (MST) in n-vertex networks of diameter D=/spl Omega/(log n), in the bounded message model. This establishes the asymptotic near-optimality of existing time-efficient distributed algorithms for the problem, whose complexity is O(D+/spl radic/nlog* n).