Constructing Degree-3 Spanners with Other Sparseness Properties
Constructing Degree-3 Spanners with Other Sparseness Properties
复制标题
构造具有其他稀疏属性的 3 级 Spanner
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
P. Heffernan
中科院分区：
文献类型：
--
作者：
G. Das;P. Heffernan
设V是k维欧氏空间中n个点的任意集合。完全欧几里得图的一个子图是t-扳手，如果对于V中的任意u和v，扳手中从u到v的最短路径的长度至多是t乘以d(u，v)。我们证明了对于任何δ>；1，存在一个多项式时间可构造的t-扳手(其中t是一个仅依赖于δ和k的常数)，并且具有下列性质。它的最大度为3，至多有n·δ条边，其总边权相当于V的最小生成树(对k≤3，其权为O(1)·wt(Mst)，对k>；3，其权为O(Logn)·wt(Mst))。
Let V be any set of n points in k-dimensional Euclidean space. A subgraph of the complete Euclidean graph is a t-spanner if for any u and v in V, the length of the shortest path from u to v in the spanner is at most t times d(u, v). We show that for any δ>1, there exists a polynomial-time constructible t-spanner (where t is a constant that depends only on δ and k) with the following properties. Its maximum degree is 3, it has at most n · δ edges, and its total edge weight is comparable to the minimum spanning tree of V (for k ≤ 3 its weight is O(1) · wt(MST), and for k>3 its weight is O(log n) · wt(MST)).