Fault-tolerant geometric spanners
Artur Czumaj, Hairong Zhao · 2003
We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces.We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for maximum degree and total cost. We present a greedy algorithm that for any t > 1 and any non-negative integer k, constructs a k-fault-tolerant t-spanner in which every vertex is of degree O(k) and whose total cost is O(k2) times the cost of minimum spanning tree; these bounds are asymptotically optimal.Our next contribution is an efficient algorithm for constructing good fault-tolerant spanners. We present a new, sufficient condition for a graph to be a k-fault-tolerant spanner. Using this condition, we design an efficient algorithm that finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bounds for the total cost.