Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Improved algorithms for constructing fault-tolerant spanners

Författare:
Publiceringsår: 2002
Språk: Engelska
Sidor: 144-156
Publikation/Tidskrift/Serie: Algorithmica
Volym: 32
Nummer: 1
Dokumenttyp: Artikel
Förlag: Spreinger-Verlag

Sammanfattning

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.

Disputation

Nyckelord

  • Mathematics and Statistics
  • well-separated pairs
  • fault-tolerance
  • computational geometry
  • spanners

Övriga

Published
Yes
  • ISSN: 0178-4617

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen