Reliable Spanners: Locality-Sensitive Orderings Strike Back
Reliable Spanners: Locality-Sensitive Orderings Strike Back
复制标题
可靠的扳手：区域敏感订单的反击
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hung Le
中科院分区：
文献类型：
--
作者：
Arnold Filtser;Hung Le
网络的一个非常理想的特性是对故障的鲁棒性。考虑一个度量空间$(X, d_X)$，基于$X$的图$H$是一个$\vartheta$-可靠的$t$-生成树，如果对于每一组故障顶点$B\subset X$，存在一个超集$B^+\supseteq B$，使得诱导子图$H[X\setminus B]$将$X\setminus B^+$中各点之间的所有距离保持在拉伸因子$t$以内，同时$B^+$的期望大小至多为$(1 + \vartheta)|B|$。这样的生成树能够承受一场灾难：即使网络90%的部分出现故障。布钦、哈 - 佩莱德和奥拉（2019年，2020年）利用局部敏感排序为欧几里得空间构建了拉伸为$1 + \epsilon$的非常稀疏的可靠生成树。哈 - 佩莱德和奥拉（2020年）利用稀疏覆盖为各种非欧几里得度量空间构建了可靠生成树。然而，第二种方法固有地依赖于宽高比（又名分布范围），并且给出了次优的拉伸和稀疏性参数。我们的贡献有两方面：
A highly desirable property of networks is robustness to failures. Consider a metric space ( X,d X ) , a graph H over X is a ϑ -reliable t -spanner if, for every set of failed vertices B ⊂ X , there is a superset B + ⊇ B such that the induced subgraph H [ X ∖ B ] preserves all the distances between points in X ∖ B + up to a stretch factor t , while the expected size of B + is as most ( 1 + ϑ )∣ B ∣ . Such a spanner could withstand a catastrophe: failure of even 90% of the network. Buchin, Har-Peled, and Ol´ah [2019,2020], constructed very sparse reliable spanners with stretch 1 + (cid:15) for Euclidean space using locality-sensitive orderings. Har-Peled and Ol´ah [2020] constructed reliable spanners for various non-Euclidean metric spaces using sparse covers. However, this second approach has an inherent dependency on the aspect ratio (a.k.a. spread) and gives sub-optimal stretch and sparsity parameters. Our contribution is twofold:
登录
查看更多内容
影响因子：
0.8
作者：
Buchin, Kevin;Har-Peled, Sariel;Oláh, Dániel
通讯作者：
Oláh, Dániel
多项式时间内最优顶点容错扳手
DOI：
10.1137/1.9781611976465.174
发表时间：
2021
期刊：
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Bodwin, Greg;Dinitz, Michael;Robelle, Caleb
通讯作者：
Robelle, Caleb
适用于公制空间的可靠扳手
影响因子：
1.3
作者：
Har-Peled, Sariel;Mendel, Manor;Oláh, Dániel
通讯作者：
Oláh, Dániel
容错 Spanner 的高效且简单的算法
DOI：
10.1145/3382734.3405735
发表时间：
2020
期刊：
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Dinitz, Michael;Robelle, Caleb
通讯作者：
Robelle, Caleb