Efficient algorithms for constructing fault-tolerant geometric spanners
Christos Levcopoulos, Giri Narasimhan, Michiel Smid · 1998
Let S be a set of n points in lKd, and k m integer such that 1 5 k 5 n -2.Algorithms are given that construct fault-tolerant spanners for S. If in such a spanner at most k edges or vertices are removed, then each pair of points in the remaining graph is still connected by a short path.Our results include (i) an algorithm with running time O(n logdB1 n + kn log log n + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k edge faults, (ii) an algorithm with running time O(n logn + k2n) that constructs a spanner with O(k2n) edges, that is resilient to k vertex faults, and (iii) an algorithm with rllnning time O(n logn+&n) that constructs a spanner of degree O(s), whose total edge length is bounded by G(2) times the weight of a miuimum spanning tree of S, and that is resilient to k edge or vertex faults.Here, c is a constant that is independent of n and Ic.