# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Improved algorithms for constructing fault-tolerant spanners

(2002) In Algorithmica 32(1). p.144-156
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 Rd, 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... (More)
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 Rd, 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 Rd. 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(kn log n) time, such a spanner with O(kn log n) edges. (Less)
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
well-separated pairs, fault-tolerance, computational geometry, spanners
in
Algorithmica
volume
32
issue
1
pages
144 - 156
publisher
Springer Science and Business Media B.V.
external identifiers
• wos:000172205300009
• scopus:0038722247
ISSN
0178-4617
language
English
LU publication?
yes
id
784044ed-e453-4e02-ab9d-83c92486683b (old id 350424)
2016-04-01 11:40:23
date last changed
2021-08-25 03:11:52
```@article{784044ed-e453-4e02-ab9d-83c92486683b,
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 Rd, 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 Rd. 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(kn log n) time, such a spanner with O(kn log n) edges.},
author       = {Levcopoulos, Christos and Narasimhan, G and Smid, M},
issn         = {0178-4617},
language     = {eng},
number       = {1},
pages        = {144--156},
publisher    = {Springer Science and Business Media B.V.},
series       = {Algorithmica},
title        = {Improved algorithms for constructing fault-tolerant spanners},
volume       = {32},
year         = {2002},
}

```