{O}(k)-robust spanners in one dimension
{O}(k)-robust spanners in one dimension
复制标题
{O}(k)-一维鲁棒扳手
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Dániel Oláh
中科院分区：
文献类型：
--
作者：
K. Buchin;W. Hulshof;Dániel Oláh
欧几里得空间中一组点上的几何t - 生成树是这样一个图：对于每一对点，它都包含一条长度至多为这两点间欧几里得距离的t倍的路径。通俗地说，如果删除k个顶点仅影响O(k)个其他顶点，那么一个生成树是O(k) - 鲁棒的。我们证明，对于任意的\(ε>0\)，在任意n个点的一维集合上，存在一个具有O(\(n^{1 + ε}\))条边的O(k) - 鲁棒的1 - 生成树。此前，人们只知道存在具有O(\(n^{2}\))条边的O(k) - 鲁棒生成树，并且存在一些点集，在这些点集上任何O(k) - 鲁棒生成树都有\(Ω(nlogn)\)条边。
A geometric t-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most t times the Euclidean distance between the points. Informally, a spanner is O(k)-robust if deleting k vertices only harms O(k) other vertices. We show that on any one-dimensional set of n points, for any e>0, there exists an O(k)-robust 1-spanner with O(n1+e) edges. Previously it was only known that O(k)-robust spanners with O(n2) edges exists and that there are point sets on which any O(k)-robust spanner has Ω(nlogn) edges.