Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Improved algorithms for constructing fault-tolerant spanners

In English

Författare

Summary, in English

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2002

Språk

Engelska

Sidor

144-156

Publikation/Tidskrift/Serie

Algorithmica

Volym

32

Issue

1

Dokumenttyp

Artikel i tidskrift

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • well-separated pairs
  • fault-tolerance
  • computational geometry
  • spanners

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0178-4617