# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Small Hop-diameter Sparse Spanners for Doubling Metrics

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### 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 \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.