.png){kind=icon}
返回
Oriented Spanners
.png){kind=icon}
OA
AI
DOI：10.1007/s00453-025-01342-8.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定欧几里得平面上的点集 \( P \) 和参数 \( t \)，我们定义有向 \( t \)-spanner \( G \) 为完全双向图的定向子图，使得对于任意点对，\( G \) 中通过该点对的最短闭合路径的长度不超过完全图上 \( P \) 的最短环路的 \( t \) 倍。我们研究计算具有小有向膨胀的稀疏图的问题。由于我们能够证明在平面上对于给定边数的最小化有向膨胀是 NP 困难的，因此我们首先考虑一维点集。虽然在此设置下获得 1-spanner 是直接的，但对于五个点，这样的 spanner 无法在平面嵌入中使最左和最右的点位于外部面上。这促使我们将研究限制为在一维点集上有单页书嵌入的有向图。对于此情况，我们提出一个动态规划算法来计算最小有向膨胀的图，该算法对于 \( n \) 个点的时间复杂度为 \( \mathcal{O}(n^7) \)，并给出一个贪心算法，可在 \( \mathcal{O}(n \log n) \) 时间内计算 5-spanner。扩展这些结果最终给出了二维点集的结论：我们证明对于凸点集，贪心三角剖分会产生一个平面有向 \( t \)-spanner，其中 \( t = 7.2 \cdot t_g \)，\( t_g \) 是贪心三角剖分膨胀的上界。
Keyword:
computational geometry
Spanner
Oriented graph
Greedy triangulation
期刊
A
IF:
0.7
论文数:
56
被引数:
2.7K
机构
引用论文
.png){kind=icon}
查看更多内容