Improved algorithms for constructing faulttolerant spanners
(2002) In Algorithmica 32(1). p.144156 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 kfaulttolerant 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 kfaulttolerant spanner. For the Euclidean metric in Rd, this leads to an O (n log n + c(k) n)time algorithm that constructs a kfaulttolerant 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 kfaulttolerant 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 kfaulttolerant spanner. For the Euclidean metric in Rd, this leads to an O (n log n + c(k) n)time algorithm that constructs a kfaulttolerant 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 kfaulttolerant 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:
http://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
 wellseparated pairs, faulttolerance, computational geometry, spanners
 in
 Algorithmica
 volume
 32
 issue
 1
 pages
 144  156
 publisher
 Springer
 external identifiers

 wos:000172205300009
 scopus:0038722247
 ISSN
 01784617
 language
 English
 LU publication?
 yes
 id
 784044ede4534e02ab9d83c92486683b (old id 350424)
 date added to LUP
 20071114 13:38:40
 date last changed
 20170827 03:49:45
@article{784044ede4534e02ab9d83c92486683b, 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 kfaulttolerant 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 kfaulttolerant spanner. For the Euclidean metric in Rd, this leads to an O (n log n + c(k) n)time algorithm that constructs a kfaulttolerant 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 kfaulttolerant 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 = {01784617}, keyword = {wellseparated pairs,faulttolerance,computational geometry,spanners}, language = {eng}, number = {1}, pages = {144156}, publisher = {Springer}, series = {Algorithmica}, title = {Improved algorithms for constructing faulttolerant spanners}, volume = {32}, year = {2002}, }