User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Journal Article

Small Hop-diameter Sparse Spanners for Doubling Metrics


Chan,  T.-H. Hubert
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Chan, T.-H.-H. (2009). Small Hop-diameter Sparse Spanners for Doubling Metrics. Discrete and Computational Geometry, 41(1), 28-44. doi:10.1007/s00454-008-9115-5.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18CA-5
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 \emph{hop diameter} bounded by $D$ if every pair of nodes has such a short path that also uses at most $D$ edges. We consider the problem of constructing sparse $(1+\eps)$-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 < \eps < 1$, one can find $(1 + \eps)$-spanner for the metric with nearly linear number of edges (i.e., only $O(n \log^* n + n\eps^{-O(k)})$ edges) and \emph{constant} hop diameter; we can also obtain a $(1 + \eps)$-spanner with linear number of edges (i.e., only $n\eps^{-O(k)}$ edges) that achieves a hop diameter that grows like the functional inverse of Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal.