Small Hop-diameter Sparse Spanners for Doubling Metrics
Lists
Only you see this
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 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+ε)-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<ε<1, one can find (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog * n+n ε −O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n ε −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.
BibTeX
@inproceedings{chan2006small,
author = {T.-H. Hubert Chan and Anupam Gupta},
title = {{Small Hop-diameter Sparse Spanners for Doubling Metrics}},
booktitle = {SODA},
year = {2006},
}| Light Spanners with Small Hop-Diameter | arXiv · 2025 |
| Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound | arXiv · 2021 |
| A Tight Lower Bound for Doubling Spanners | arXiv · 2025 |
| Greedy spanners are optimal in doubling metrics | arXiv · 2017 |
| A light metric spanner | arXiv · 2015 |
| The Greedy Spanner is Existentially Optimal | arXiv · 2016 |