Improved algorithms for constructing fault-tolerant spanners
Levcopoulos, Christos LU
; Narasimhan, G
and Smid, M
(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)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/350424
- author
- Levcopoulos, Christos
LU
; Narasimhan, G
and Smid, M
- organization
- publishing date
- 2002
- 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
- external identifiers
-
- wos:000172205300009
- scopus:0038722247
- ISSN
- 0178-4617
- language
- English
- LU publication?
- yes
- id
- 784044ed-e453-4e02-ab9d-83c92486683b (old id 350424)
- date added to LUP
- 2016-04-01 11:40:23
- date last changed
- 2022-01-26 08:33:43
@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}},
keywords = {{well-separated pairs; fault-tolerance; computational geometry; spanners}},
language = {{eng}},
number = {{1}},
pages = {{144--156}},
publisher = {{Springer}},
series = {{Algorithmica}},
title = {{Improved algorithms for constructing fault-tolerant spanners}},
volume = {{32}},
year = {{2002}},
}