Reliable Spanners for Metric Spaces
Reliable Spanners for Metric Spaces
复制标题
适用于公制空间的可靠扳手
DOI：
10.1145/3563356
复制
发表时间：
2023
影响因子：
1.3
通讯作者：
Oláh, Dániel
中科院分区：
文献类型：
--
作者：
Har-Peled, Sariel;Mendel, Manor;Oláh, Dániel
如果扳手能够承受网络中的大型灾难性故障，那么它就是可靠的。更准确地说，一些节点的任何故障都只会在剩余的图中造成很小的伸缩破坏。换句话说，对于残差图中的几乎所有节点，都会维护扳手属性。在低维欧几里得环境中，已知具有近线性尺寸的可靠扳手的构造。在这里，我们给出了平面图、树和(一般)度量空间的可靠扳手的新构造。
A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation. In other words, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees, and (general) metric spaces.
登录
查看更多内容
最佳顶点容错扳手（用于固定拉伸）
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Gregory Bodwin;M. Dinitz;M. Parter;V. V. Williams
通讯作者：
V. V. Williams
可靠的扳手：区域敏感订单的反击
DOI：
--
发表时间：
2021
期刊：
arXiv.org
影响因子：
--
作者：
Arnold Filtser;Hung Le
通讯作者：
Hung Le
Ramsey 分区和邻近数据结构
DOI：
--
发表时间：
2005
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
M. Mendel;A. Naor
通讯作者：
A. Naor
影响因子：
0.8
作者：
Buchin, Kevin;Har-Peled, Sariel;Oláh, Dániel
通讯作者：
Oláh, Dániel
DOI：
10.1137/siap
发表时间：
2020
期刊：
Jyväskylä studies in education, psychology and social research
影响因子：
--
作者：
김성연
通讯作者：
김성연