File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1145/1109557.1109566
 Scopus: eid_2s2.033244489812
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Small hopdiameter sparse spanners for doubling metrics
Title  Small hopdiameter sparse spanners for doubling metrics 

Authors  
Keywords  Asymptotic Stability Function Evaluation Linear Equations Problem Solving 
Issue Date  2006 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms (SODA '06), Miami, FL, 2224 January 2006. In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2006, p. 7078 How to Cite? 
Abstract  Given a metric M = (V, d), a graph G = (V, E) is a tspanner 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 Identifier  http://hdl.handle.net/10722/92657 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, THH  en_HK 
dc.contributor.author  Gupta, A  en_HK 
dc.date.accessioned  20100917T10:53:14Z   
dc.date.available  20100917T10:53:14Z   
dc.date.issued  2006  en_HK 
dc.identifier.citation  Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms (SODA '06), Miami, FL, 2224 January 2006. In Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 2006, p. 7078  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/92657   
dc.description.abstract  Given a metric M = (V, d), a graph G = (V, E) is a tspanner 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.language  eng  en_HK 
dc.publisher  Society for Industrial and Applied Mathematics.   
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.subject  Asymptotic Stability  en_HK 
dc.subject  Function Evaluation  en_HK 
dc.subject  Linear Equations  en_HK 
dc.subject  Problem Solving  en_HK 
dc.title  Small hopdiameter sparse spanners for doubling metrics  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chan, THH:hubert@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, THH=rp01312  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1145/1109557.1109566   
dc.identifier.scopus  eid_2s2.033244489812  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033244489812&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  70  en_HK 
dc.identifier.epage  78  en_HK 
dc.identifier.scopusauthorid  Chan, THH=12645073600  en_HK 
dc.identifier.scopusauthorid  Gupta, A=8354044800  en_HK 