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*^{2}*n*log *n*) edges. The analysis only uses basic notions from probability theory.