Small hop-diameter sparse spanners for doubling metrics

T. H.Hubert Chan, Anupam Gupta

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)28-44
Number of pages17
JournalDiscrete and Computational Geometry
Volume41
Issue number1
DOIs
StatePublished - Jan 2009

Keywords

  • Algorithms
  • Doubling metrics
  • Hop diameter
  • Sparse spanners

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Small hop-diameter sparse spanners for doubling metrics'. Together they form a unique fingerprint.

Cite this