Improving the Stretch Factor of a Geometric Network by Edge Augmentation
Improving the Stretch Factor of a Geometric Network by Edge Augmentation
复制标题
通过边缘增强提高几何网络的拉伸因子
DOI：
10.1137/050635675
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Joachim Gudmundsson
中科院分区：
文献类型：
--
作者：
M. Farshi;P. Giannopoulos;Joachim Gudmundsson
给定$\mathbb{R}^d$中具有$n$个顶点和$m$条边的欧几里得图$G$，我们考虑向$G$添加一条边以使所得图的拉伸因子最小化的问题。目前，用于计算具有正边权重的图的拉伸因子的最快算法在$\cal{O}$$（nm+n^2 \log n）$时间内运行，导致用于计算最优边的平凡$\cal{O}$（n^3m+n^4 \log n）$时间算法。首先，我们证明了一个简单的修改产生的最优解在$\cal{O}$$（n^4）$时间使用$\cal{O}$$（n^2）$空间。为了减少运行时间，我们考虑几个近似算法。
Given a Euclidean graph $G$ in $\mathbb{R}^d$ with $n$ vertices and $m$ edges, we consider the problem of adding an edge to $G$ such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in $\cal{O}$$(nm+n^2 \log n)$ time, resulting in a trivial $\cal{O}$$(n^3m+n^4 \log n)$-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in $\cal{O}$$(n^4)$ time using $\cal{O}$$(n^2)$ space. To reduce the running time we consider several approximation algorithms.