Distributed Spanner Construction in Doubling Metric Spaces
Distributed Spanner Construction in Doubling Metric Spaces
复制标题
加倍度量空间中的分布式 Spanner 构造
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Sriram V. Pemmaraju
中科院分区：
文献类型：
--
作者：
Mirela Damian;Saurav Pandit;Sriram V. Pemmaraju
本文提出了一种分布式算法，该算法在驻留在常量倍维度量空间中的 n 节点单位球图 (UBG) G 上运行，并针对任何 e 0 构造 G 的 (1 + e)-spanner H，其最大度以常量为界。此外，我们证明 H 在以下意义上是“轻量级的”。设 Δ 表示 G 的长宽比，即 G 中最长边的长度与 G 中最短边的长度之比。 H 的总权重由 O(logΔ) · wt(MST) 界定，其中 MST 表示度量空间的最小生成树。最后，我们证明 H 满足所谓的蛙跳性质，直接的含义是，对于具有固定维数的欧几里得度量空间的特殊情况，H 的权重以 O(wt(MST)) 为界。因此，当前的结果包含了作者在 PODC 2006 中适用于欧几里得度量空间的结果，并将这些结果扩展到具有常数倍维的度量空间。
This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any e 0, a (1 + e)-spanner H of G with maximum degree bounded above by a constant. In addition, we show that H is “lightweight”, in the following sense. Let Δ denote the aspect ratio of G, that is, the ratio of the length of a longest edge in G to the length of a shortest edge in G. The total weight of H is bounded above by O(logΔ) · wt(MST), where MST denotes a minimum spanning tree of the metric space. Finally, we show that H satisfies the so called leapfrog property, an immediate implication being that, for the special case of Euclidean metric spaces with fixed dimension, the weight of H is bounded above by O(wt(MST)). Thus, the current result subsumes the results of the authors in PODC 2006 that apply to Euclidean metric spaces, and extends these results to metric spaces with constant doubling dimension.