Note: |
|
(LaTeX) 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. |
URL for the Abstract: |
|
Categories,
Keywords: |
Algorithms, Sparse spanners, Doubling metrics, Hop diameter |
HyperLinks / References / URLs: |
|
Copyright Message: |
© The Author(s) 2008. This article is published with open access at Springerlink.com |
Personal Comments: |
|
Download
Access Level: |
Public |
|