Fault-tolerant geometric spanners (Q1762946)

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 \({\mathcal O}(k)\) and whose total cost is \({\mathcal O}(k^2)\) times the cost of the 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 bound for the total cost.