Fault-tolerant spanners for general graphs
Shiri Chechik, Michael L. Langberg, David Peleg, Liam Roditty · 2009
The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,v) for every u,v ∈ V, where δG'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n1+1/k), and this size-stretch tradeoff is conjectured to be tight.