On hierarchical routing in doubling metrics

Hubert T.H. Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou

Research output: Contribution to conferencePaperpeer-review


We study the problem of routing in doubling metrics, and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with small amount of routing information stored at each vertex). We say that a metric (X, d) has doubling dimension dim(X) at most α if every set of diameter D can be covered by 2 α sets of diameter D/2. (A doubling metric is one whose doubling dimension dim(X) is a constant.) We show how to perform (1 + τ)-stretch routing on metrics for any 0 < τ ≤ 1 with routing tables of size at most (α/τ) O(α) log 2 Δ bits with only (α/τ) o(α) log Δ entries, where Δ is the diameter of the graph; hence the number of routing table entries is just τ ;-o(1) log Δ for doubling metrics. These results extend and improve on those of Talwar (2004). We also give better constructions of sparse spanners for doubling metrics than those obtained from the routing tables above; for τ > 0, we give algorithms to construct (1 + τ)stretch spanners for a metric (X, d) with maximum degree at most (2 + 1/τ) O(dim(X)), matching the results of Das et al. for Euclidean metrics.

Original languageEnglish (US)
Number of pages10
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'On hierarchical routing in doubling metrics'. Together they form a unique fingerprint.

Cite this