Advanced

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:
author
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
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
2007-11-14 13:38:40
date last changed
2017-08-27 03:49:45
@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},
  keyword      = {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},
}