M. A. Abam
ABSTRACT
We introduce the concept of region-fault tolerant spanners for planar point sets, and prove the existence of region-fault tolerant spanners of small size. For a geometric graph G on a point set P and a region F, we define G ⊖ F to be what remains of G after the vertices and edges of G intersecting F have been removed. A C-fault tolerant t-spanner is a geometric graph G on P such that for any convex region F, the graph G ⊖ F is a t-spanner for Gc(P)⊖F, where Gc(P) is the complete geometric graph on P. We prove that any set P of n points admits a C-fault tolerant (1 + ε)-spanner of size O(n log n), for any constant ε > 0; if adding Steiner points is allowed then the size of the spanner reduces to O(n), and for several special cases we show how to obtain region-fault tolerant spanners of O(n) size without using Steiner points. We also consider fault-tolerant geodesic t-spanners: this is a variant where, for any disk D, the distance in G ⊖ D between any two points u, v ε P \ D is at most t times the geodesic distance between u and v in R2 \ D. We prove that for any P we can add O(n) Steiner points to obtain a fault-tolerant geodesic (1 + ε)-spanner of size O(n).
- Region-fault tolerant geometric spanners
Recommendations
Region-Fault Tolerant Geometric Spanners
We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant spanners of small size. For a geometric graph $\mathcal{G}$ on a point set P and a region F, we define $\mathcal{G}\ominus ...
Fault-tolerant spanners for general graphs
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,...
Fault-Tolerant Geometric Spanners
We present two new results about vertex and edge fault-tolerant spanners in Euclidean spaces. We describe the first construction of vertex and edge fault-tolerant spanners having optimal bounds for maximum degree and total cost. We present a greedy ...
Comments