论文标题
可靠的度量空间跨度
Reliable Spanners for Metric Spaces
论文作者
论文摘要
如果Spanner可以承受网络中的大型灾难性故障，那么它将可靠。更确切地说，某些节点的任何故障只能根据扩张而在其余图中造成较小的损坏，即，在残留图中，几乎所有节点都维持了扳手属性。在低维欧几里得设置中已知可靠的跨度跨度的构造。在这里，我们为平面图，树木和（一般）度量空间提供了可靠的跨度的新结构。
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, that is, 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.
