Improved Algorithms for Constructing Fault-Tolerant Spanners |
| |
Authors: | Levcopoulos Narasimhan Smid |
| |
Affiliation: | (1) Department of Computer Science, Lund University, Box 118, S-22100 Lund, Sweden. Christos.Levcopoulos@dna.lth.se., SE;(2) Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA. giri@msci.memphis.edu., US;(3) Department of Computer Science, University of Magdeburg, D-39106 Magdeburg, Germany. michiel@isg.cs.uni-magdeburg.de., DE |
| |
Abstract: | Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R d , this leads to an O(n log n + c k n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c k ) , whose total edge length is O(c k ) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R d . These algorithms construct (i) in O(n log n + k 2 n) time, a k -fault-tolerant spanner with O(k 2 n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges. |
| |
Keywords: | . Computational geometry Spanners Fault-tolerance Well-separated pairs. |
本文献已被 SpringerLink 等数据库收录! |
|