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 such short path 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 a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε-O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε-O(k) edges) which achieves a hop diameter that grows like the functional inverse of the 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 |