Distributed Construction of Light Networks
Distributed Construction of Light Networks
复制标题
光网络的分布式构建
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ofer Neiman
中科院分区：
文献类型：
--
作者：
Michael Elkin;Arnold Filtser;Ofer Neiman
加权图G =（V，E，w）的t-H是一个子图，它的所有两两距离都近似到一个因子t。H的亮度定义为H的权重与最小生成树的权重之比。（α，β）-浅光树（英语：（α，β）-Shallow Light Tree）是一棵亮度为β的树，它近似从指定的根顶点到因子α的所有距离。一长串的工作产生了有效的算法，产生（几乎）最佳的光spectrum和SLT。一些最值得注意的算法应用的光spectrum和SLT是在分布式设置。令人惊讶的是，到目前为止，还没有已知的有效的分布式算法来构建这些对象的一般图。在本文中，我们设计了有效的分布式算法，在CONGEST模型构建光spectrum和SLT，接近最佳的参数。具体地说，对于任何k ≥ 1和0 < ∈ < 1，我们证明了一个亮度为O（k·n1/k）的（2k − 1）·（1 + ∈）-矩阵可以在[EQUATION]轮中构建（其中n =| V| D是G的跳跃直径）。对于任何α > 1，我们提供一个[方程]轮。我们的算法的运行时间不能得到实质性的改善。我们还考虑了加倍图族的空间，并在CONGEST模型中设计了一个[EQUATION]轮算法，该算法计算亮度为（log n）/∈O（1）的（1 + ∈）-空间。作为一个垫脚石，这是有趣的，在其本身的权利，我们首先开发一个分布式算法构建网络（任意加权图），推广以前的算法，只适用于未加权图。
A t-spanner H of a weighted graph G = (V, E, w) is a subgraph that approximates all pairwise distances up to a factor of t. The lightness of H is defined as the ratio between the weight of H to that of the minimum spanning tree. An (α, β)-Shallow Light Tree (SLT) is a tree of lightness β, that approximates all distances from a designated root vertex up to a factor of α. A long line of works resulted in efficient algorithms that produce (nearly) optimal light spanners and SLTs. Some of the most notable algorithmic applications of light spanners and SLTs are in distributed settings. Surprisingly, so far there are no known efficient distributed algorithms for constructing these objects in general graphs. In this paper we devise efficient distributed algorithms in the CONGEST model for constructing light spanners and SLTs, with near optimal parameters. Specifically, for any k ≥ 1 and 0 < ∈ < 1, we show a (2k − 1) · (1 + ∈)-spanner with lightness O(k·n1/k) can be built in [EQUATION] rounds (where n = |V| and D is the hop-diameter of G). In addition, for any α > 1 we provide an [EQUATION] rounds. The running times of our algorithms cannot be substantially improved. We also consider spanners for the family of doubling graphs, and devise a [EQUATION] rounds algorithm in the CONGEST model that computes a (1 + ∈)-spanner with lightness (log n)/∈O(1). As a stepping stone, which is interesting in its own right, we first develop a distributed algorithm for constructing nets (for arbitrary weighted graphs), generalizing previous algorithms that worked only for unweighted graphs.