Loading...
Please wait, while we are loading the content...
Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree (2012)
| Content Provider | CiteSeerX |
|---|---|
| Author | Chan, T. -H. Hubert Li, Mingfei Ning, Li |
| Description | In ICALP We study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k, t)-VFTS or simply k-VFTS), if for any subset S â X with S ⤠k, it holds that dH\S(x, y) ⤠t · d(x, y), for any pair of x, y â X \ S. For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m ⥠2n, we can reduce the hop-diameter of the above k-VFTS to O(α(m, n)) by adding O(km) edges, where α is a functional inverse of the Ackermannâs function. Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k 2 n) edges and maximum degree O(k²). |
| File Format | |
| Language | English |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Subject Keyword | Bounded Hop-diameter Bounded Maximum Degree Ackermann Function Euclidean Spanner Maximum Degree First Time Functional Inverse K-vertex-fault-tolerant T-spanner Basic K-vfts Sparse Fault-tolerant Spanner Basic Construction Metric Space Fault-tolerant Spanner Fault-tolerant Single-sink Spanner |
| Content Type | Text |
| Resource Type | Article |
