Computing Lightweight Spanners Locally
Computing Lightweight Spanners Locally
复制标题
本地计算轻量级 Spanner
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Ge Xia
中科院分区：
文献类型：
--
作者：
Iyad A. Kanj;Ljubomir Perković;Ge Xia
考虑了在局部分布式计算模型下计算单位圆盘图的有界度轻量平面空间的问题。我们的动机的假设，这样的子图可以提供有效的单播和组播在无线分布式系统的底层网络拓扑结构。我们提出了第一个局部分布式算法，计算一个给定的单位圆盘图的有界度平面轻量图。度的上界、拉伸因子和权重的上界都非常小。例如，我们的结果意味着一个局部分布式算法，计算一个给定的单位圆盘图U的平面图，其度最多为14，拉伸因子最多为8.81，权重最多为V（U）的欧氏最小生成树的权重的8.81倍。
通过给出一个O（nlogn）时间集中的算法，我们展示了我们的技术的更广泛的应用，该算法构造了单位盘图（包括欧几里得图）的有界度平面轻量级spectum，并具有最好的上界，拉伸因子和权重。
We consider the problem of computing bounded-degree lightweight plane spanners of unit disk graphs in the local distributed model of computation. We are motivated by the hypothesis that such subgraphs can provide the underlying network topology for efficient unicasting and multicasting in wireless distributed systems. We present the firstlocal distributed algorithm that computes a bounded-degree plane lightweight spanner of a given unit disk graph. The upper bounds on the degree, the stretch factor, and the weight of the spanner, are very small. For example, our results imply a local distributed algorithm that computes a plane spanner of a given unit disk graph U, whose degree is at most 14, stretch factor at most 8.81, and weight at most 8.81 times the weight of a Euclidean Minimum Spanning Tree of V(U).
We show a wider application of our techniques by giving an O(nlogn) time centralized algorithm that constructs bounded-degree plane lightweight spanners of unit disk graphs (which include Euclidean graphs), with the bestupper bounds on the spanner degree, stretch factor, and weight.