A Spanner for the Day After
A Spanner for the Day After
复制标题
后天的扳手
DOI：
10.1007/s00454-020-00228-6
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Oláh, Dániel
中科院分区：
文献类型：
--
作者：
Buchin, Kevin;Har-Peled, Sariel;Oláh, Dániel
我们将展示如何在一组断点上构造一个扳手，该扳手对节点的灾难性故障具有弹性。具体来说，对于规定的参数，计算出的扳手有$$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$条边。此外，对于任意点和任意删除的集合点，残差图对除它们之外的所有点都是有效的。除了琐碎的团块边缘之外，以前的构造都没有这种弹性特性（即，只有一小部分额外的顶点失去了保持距离的连通性）。我们的构造首先在一个维度上解决了确切的问题，然后在更高的维度上展示了一个令人惊讶的简单而优雅的构造，它以黑盒的方式使用了一维构造。
We show how to construct a-spanner over a setofnpoints inthat is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters, the computed spannerhas $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$edges. Furthermore, foranyk, andanydeleted setofkpoints, the residual graphis a-spanner for all the points ofexcept forof them. No previous constructions, beyond the trivial clique withedges, were known with this resilience property (i.e., only a tiny additional fraction of vertices,, lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion.
登录
查看更多内容
DOI：
--
发表时间：
2005
期刊：
Computational geometry
影响因子：
--
作者：
B. Aronov;M. D. Berg;O. Cheong;Joachim Gudmundsson;H. Haverkort;M. Smid;A. Vigneron
通讯作者：
A. Vigneron
DOI：
10.1137/s0097539700382947
发表时间：
2002-05
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
通讯作者：
Joachim Gudmundsson;C. Levcopoulos;G. Narasimhan
DOI：
--
发表时间：
1999
期刊：
Computational geometry
影响因子：
--
作者：
S. Arya;David M. Mount;M. Smid
通讯作者：
M. Smid
DOI：
--
发表时间：
1998
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
C. Levcopoulos;G. Narasimhan;M. Smid
通讯作者：
M. Smid
{O}(k)-一维鲁棒扳手
DOI：
--
发表时间：
2018
期刊：
影响因子：
--
作者：
K. Buchin;W. Hulshof;Dániel Oláh
通讯作者：
Dániel Oláh