论文标题
通过添加边缘来改善公制图的扩张
Improving the dilation of a metric graph by adding edges
论文作者
论文摘要
有关跨越的大多数文献都专注于从头开始构建图形。相反，本文着重于添加边缘以改进现有图形。该领域的一个主要开放问题是：给定一个嵌入在公制空间中的图，预算为$ k $边缘，我们添加了哪些$ k $边缘以产生最低涂抹图？过去已经研究了$ k = 1 $的特殊情况，但没有以$ k> 1美元的重大突破。我们提供了第一个积极的结果，即以$ O（n^3 \ log n）$时间运行的$ O（k）$ - 近似算法。
Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of $k$ edges, which $k$ edges do we add to produce a minimum-dilation graph? The special case where $k=1$ has been studied in the past, but no major breakthroughs have been made for $k > 1$. We provide the first positive result, an $O(k)$-approximation algorithm that runs in $O(n^3 \log n)$ time.
