A randomized construction of fault-tolerant spanners

Michiel Smid

Given a set S of points in R^d and a positive integer k, a graph G=(S,E) is called a fault-tolerant spanner, if for every subset S' of S having size at most k, the graph G\S' is a spanner for the point set S\S'. I will present a recent result of Dinitz and Krauthgamer: A simple randomized algorithm that converts, with high probability, an arbitrary spanner into a fault-tolerant spanner with O(k²nlog n) edges. The analysis only uses basic notions from probability theory.