Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
We study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k,t)-VFTS or simply k-VFTS), if for any subset S?X with |S|?k, it holds that d H?S (x,y)?t?d(x,y), for any pair of x,y?X?S.
sparse fault-tolerant spanners bounded hop-diameter doubling dimension bounded maximum degree