Efficient algorithms for constructing fault-tolerant geometric spanners
- 1 January 1998
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 186-195
- https://doi.org/10.1145/276698.276734
Abstract
Let S be a set of n points in IRd, and k an integersuch that 1 k n \Gamma 2. Algorithms aregiven that construct fault-tolerant spanners for S.If in such a spanner at most k edges or verticesare removed, then each pair of points in the remaininggraph is still connected by a short path.Our results include (i) an algorithm with runningtime O(n logd\Gamma1n + kn log log n + k2n) that constructsa spanner with O(k2n) edges, that is resilientto k edge faults, (ii) an...Keywords
This publication has 0 references indexed in Scilit: