On hierarchical routing in doubling metrics

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 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.link_to_subscribed_fulltex