hide
Free keywords:
-
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.
