File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: On hierarchical routing in doubling metrics

TitleOn hierarchical routing in doubling metrics
Authors
Issue Date2005
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 762-771 How to Cite?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/151858
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HTHen_US
dc.contributor.authorGupta, Aen_US
dc.contributor.authorMaggs, BMen_US
dc.contributor.authorZhou, Sen_US
dc.date.accessioned2012-06-26T06:30:09Z-
dc.date.available2012-06-26T06:30:09Z-
dc.date.issued2005en_US
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2005, p. 762-771en_US
dc.identifier.urihttp://hdl.handle.net/10722/151858-
dc.description.abstractWe 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.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleOn hierarchical routing in doubling metricsen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HTH:hubert@cs.hku.hken_US
dc.identifier.authorityChan, HTH=rp01312en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-20744437429en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-20744437429&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage762en_US
dc.identifier.epage771en_US
dc.identifier.scopusauthoridChan, HTH=12645073600en_US
dc.identifier.scopusauthoridGupta, A=8354044800en_US
dc.identifier.scopusauthoridMaggs, BM=7003544820en_US
dc.identifier.scopusauthoridZhou, S=23468215300en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats