论文标题
用于离散半径的线性时间算法在度量空间中最佳增强路径
A Linear-Time Algorithm for Discrete Radius Optimally Augmenting Paths in a Metric Space
论文作者
论文摘要
让$ p $是嵌入度量空间中的$ n $顶点的路径图。我们考虑将新的边缘添加到$ p $的问题，以使所得图的半径最小化，其中任何中心都被限制为$ p $的顶点之一。以前，研究中心可能是图形边缘内部的一个点的“连续”版本，并已知线性时间算法。我们的“离散”问题以前尚未研究。我们为问题提供了线性时间算法。
Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of $P$. Previously, the "continuous" version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our "discrete" version of the problem has not been studied before. We present a linear-time algorithm for the problem.
