.png){kind=icon}
返回
Optimal Euclidean Tree Covers
.png){kind=icon}
PRE
AI
DOI：10.1007/s00454-025-00803-9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
一个度量空间的 (1+epsilon) 树覆盖是一组树，其中每对点在其中一棵树中有一条 (1+epsilon) 路径。著名的哑铃定理 [Arya et al. STOC'95] 表明，任何 d 维欧几里得空间中的 n 个点集都存在一个 (1+epsilon) 树覆盖，包含 Od(epsilon-d·log(1/epsilon)) 棵树，其中 Od 表示忽略仅依赖于维度 d 的项。其构造的运行时间为 Od(n log n·log(1/epsilon)/epsilond + n·epsilon-2d)。由于同一个点可能出现在树的多个层级中，树覆盖中点的最大度数可能高达 Omega(log Phi)，其中 Phi 是输入点集的纵横比。在本工作中，我们提出一个包含 Od(epsilon-d+1·log(1/epsilon)) 棵树的 (1+epsilon) 树覆盖，这是最优的（忽略 log(1/epsilon) 因子）。此外，任意树中点的最大度数为与 d 无关的绝对常数。作为直接推论，我们在低维欧几里得空间中获得一个最优路由方案。我们还提出一个包含 Od(epsilon(-d+1)/2·log(1/epsilon)) 棵树的 (1+epsilon) Steiner 树覆盖（可使用 Steiner 点），这也是最优的。我们的两种构造的运行时间与各自树覆盖的边数成线性关系，忽略一个 Od(n log n) 的加性项；这优于哑铃定理的运行时间。
Keyword:
Spanners
Tree covers
Compact routing
Metric embedding
期刊
D
IF:
0.6
论文数:
63
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容