Item

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.