File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: On hierarchical routing in doubling metrics
Title  On hierarchical routing in doubling metrics 

Authors  
Issue Date  2005 
Citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2005, p. 762771 How to Cite? 
Abstract  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. 
Persistent Identifier  http://hdl.handle.net/10722/151858 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, HTH  en_US 
dc.contributor.author  Gupta, A  en_US 
dc.contributor.author  Maggs, BM  en_US 
dc.contributor.author  Zhou, S  en_US 
dc.date.accessioned  20120626T06:30:09Z   
dc.date.available  20120626T06:30:09Z   
dc.date.issued  2005  en_US 
dc.identifier.citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2005, p. 762771  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/151858   
dc.description.abstract  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.  en_US 
dc.language  eng  en_US 
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_US 
dc.title  On hierarchical routing in doubling metrics  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Chan, HTH:hubert@cs.hku.hk  en_US 
dc.identifier.authority  Chan, HTH=rp01312  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.scopus  eid_2s2.020744437429  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.020744437429&selection=ref&src=s&origin=recordpage  en_US 
dc.identifier.spage  762  en_US 
dc.identifier.epage  771  en_US 
dc.identifier.scopusauthorid  Chan, HTH=12645073600  en_US 
dc.identifier.scopusauthorid  Gupta, A=8354044800  en_US 
dc.identifier.scopusauthorid  Maggs, BM=7003544820  en_US 
dc.identifier.scopusauthorid  Zhou, S=23468215300  en_US 