Distributed Algorithms for Low Stretch Spanning Trees
Distributed Algorithms for Low Stretch Spanning Trees
复制标题
低伸展生成树的分布式算法
DOI：
10.4230/lipics.disc.2019.4
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
C. Lenzen
中科院分区：
文献类型：
--
作者：
R. Becker;Y. Emek;M. Ghaffari;C. Lenzen
给定一个整数边长的无向图，基于拉伸的概念，研究了用生成树逼近图中距离的问题。我们的主要贡献是一个分布式算法中的CONGEST模型的计算，构造一个随机生成树的保证，预期的拉伸的每一个边缘是O（log 3 n），其中n是在图中的节点数。如果图是未加权的，则该算法可以实现为O（D）轮，其中D是图的跳直径，因此是渐近最优的。在加权的情况下，我们的算法的运行时间与当前已知的精确距离计算的界限相匹配，即，（min{我们强调，这是第一次分布式建设的生成树，导致多对数预期拉伸与非平凡的运行时间。2012 ACM学科分类计算数学→图算法;计算理论→分布式算法
Given an undirected graph with integer edge lengths, we study the problem of approximating the distances in the graph by a spanning tree based on the notion of stretch. Our main contribution is a distributed algorithm in the CONGEST model of computation that constructs a random spanning tree with the guarantee that the expected stretch of every edge is O(log3 n), where n is the number of nodes in the graph. If the graph is unweighted, then this algorithm can be implemented to run in O(D) rounds, where D is the hop-diameter of the graph, thus being asymptotically optimal. In the weighted case, the run-time of our algorithm matches the currently best known bound for exact distance computations, i.e., Õ(min{ √ nD, √ nD1/4 + n3/5 + D}). We stress that this is the first distributed construction of spanning trees leading to poly-logarithmic expected stretch with non-trivial running time. 2012 ACM Subject Classification Mathematics of computing → Graph algorithms; Theory of computation → Distributed algorithms