Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Given a metric M = (V, d), a graph G = (V, E) is a t-spanner for M if every pair of nodes in V has a "short" path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every such short path also uses at most D edges. We consider the problem of constructing sparse (1 + ε)-spanners with small hop diameter for metrics of low doubling dimension.In this paper, we show that given any metric with constant doubling dimension k, and any 0 < ε < 1, one can find a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε^-O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε^-O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal.

REFERENCES

• 1: Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011789]
• 2: N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Tech. report 71/87, 1987.
• 3: 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]
• 4: 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]
• 5: Patrice Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4):429--448, 1983.
• 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: Hubert T-H. Chan , Anupam Gupta , Bruce M. Maggs , Shuheng Zhou, On hierarchical routing in doubling metrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: 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]
• 9: Bernard Chazelle. Computing on a free tree via complexity-preserving mappings. In Algorithmica 2, pages 337--361, 1987.
• 10: K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom., 22(1):63--93, 1999.
• 11: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 12: Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064117]
• 13: J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.
• 14: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 15: Robert Krauthgamer and James R. Lee. The black-box complexity of nearest neighbor search. In ICALP, pages 858--869, 2004.
• 16: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 17: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 18: D. Peleg and A. Schäffer. Graph spanners. In J. Graph Theory 13, pages 99--116, 1989.
• 19: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 20: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 21: J.S. Salowe. Constructing multidimensional spanner graphs. In Internat. J. Comput. Geom. Appl. 1, pages 99--107, 1991.
• 22: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]
• 23: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 24: Pravin M. Vaidya, A sparse graph almost as good as the complete graph on points in K dimensions, Discrete & Computational Geometry, v.6 n.4, p.369-381, 1991 [doi>10.1007/BF02574695]
• 25: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory