File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Small hop-diameter sparse spanners for doubling metrics

TitleSmall hop-diameter sparse spanners for doubling metrics
Authors
KeywordsAsymptotic Stability
Function Evaluation
Linear Equations
Problem Solving
Issue Date2006
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 70-78 How to Cite?
AbstractGiven 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 such short path 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 a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε -O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε -O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal.
Persistent Identifierhttp://hdl.handle.net/10722/92657
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorGupta, Aen_HK
dc.date.accessioned2010-09-17T10:53:14Z-
dc.date.available2010-09-17T10:53:14Z-
dc.date.issued2006en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 70-78en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92657-
dc.description.abstractGiven 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 such short path 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 a (1 + ε)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + nε -O(k)) edges) and a constant hop diameter, and also a (1 + ε)-spanner with linear number of edges (i.e., only nε -O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal.en_HK
dc.languageengen_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.subjectAsymptotic Stabilityen_HK
dc.subjectFunction Evaluationen_HK
dc.subjectLinear Equationsen_HK
dc.subjectProblem Solvingen_HK
dc.titleSmall hop-diameter sparse spanners for doubling metricsen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33244489812en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33244489812&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage70en_HK
dc.identifier.epage78en_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridGupta, A=8354044800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats