Fault-tolerant geometric spanners

ABSTRACT

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 algorithm that for any t > 1 and any non-negative integer k, constructs a k-fault-tolerant t-spanner in which every vertex is of degree O(k) and whose total cost is O(k²) times the cost of minimum spanning tree; these bounds are asymptotically optimal.Our next contribution is an efficient algorithm for constructing good fault-tolerant spanners. We present a new, sufficient condition for a graph to be a k-fault-tolerant spanner. Using this condition, we design an efficient algorithm that finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bounds for the total cost.

REFERENCES

• 1: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 2: Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225191]
• 3: Sunil Arya , David M. Mount , Michiel Smid, Dynamic algorithms for geometric spanners of small diameter: randomized solutions, Computational Geometry: Theory and Applications, v.13 n.2, p.91-107, June 1999 [doi>10.1016/S0925-7721(99)00014-0]
• 4: S. Arya and M. Smid. Efficient construction of a bounded-degree spanner with low weight. Algorithmica, 17(1):33--54, 1997.
• 5: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
• 7: Barun Chandra , Gautam Das , Giri Narasimhan , José Soares, New sparseness results on graph spanners, Proceedings of the eighth annual symposium on Computational geometry, p.192-201, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142717]
• 8: P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
• 9: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 10: Artur Czumaj , Andrzej Lingas, Fast Approximation Schemes for Euclidean Multi-connectivity Problems, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.856-868, July 09-15, 2000
• 11: Gautam Das , Paul Heffernan , Giri Narasimhan, Optimally sparse spanners in 3-dimensional Euclidean space, Proceedings of the ninth annual symposium on Computational geometry, p.53-62, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160998]
• 12: G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. IJCGA, 7(4):293--315, 1997.
• 13: Gautam Das , Giri Narasimhan , Jeffrey Salowe, A new way to weigh Malnourished Euclidean graphs, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.215-222, January 22-24, 1995, San Francisco, California, United States
• 14: D. Eppstein. Spanning trees and spanners. In Handbook of Computational Geometry, pp. 425--461, 1997.
• 15: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Fast Greedy Algorithms for Constructing Sparse Geometric Spanners, SIAM Journal on Computing, v.31 n.5, p.1479-1500, 2002 [doi>10.1137/S0097539700382947]
• 16: C. Levcopoulos and A. Lingas. There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees. Algorithmica, 8:251--256, 1992.
• 17: Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Efficient algorithms for constructing fault-tolerant geometric spanners, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.186-195, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276734]
• 18: Tamás Lukovszki, New Results of Fault Tolerant Geometric Spanners, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.193-204, August 11-14, 1999
• 19: K. Mehlhorn and S. Naher. Dynamic fractional cascading. Algorithmica, 5:215--241, 1990.
• 20: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 21: D. Peleg and A. Schaffer. Graph spanners. JGT, 13:99--116, 1989.
• 22: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 23: J. Ruppert and R. Seidel. Approximating the d -dimensional complete Euclidean graph. Proc 3rd CCCG, pp. 207--210, 1991.
• 24: A. C. Yao. On Constructing minimum spanning trees in k-demensional spaces and related problems. SICOMP, 11:721--736, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
computational geometry, fault-tolerant spanners, greedy algorithms, spanners