File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s00454-008-9115-5
- Scopus: eid_2-s2.0-57849150342
- WOS: WOS:000261831500002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Small hop-diameter sparse spanners for doubling metrics
Title | Small hop-diameter sparse spanners for doubling metrics |
---|---|
Authors | |
Keywords | Algorithms Doubling metrics Hop diameter Sparse spanners |
Issue Date | 2009 |
Publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm |
Citation | Discrete And Computational Geometry, 2009, v. 41 n. 1, p. 28-44 How to Cite? |
Abstract | Given 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 pair of nodes has such a short path that 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 (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog∈ * n+n ε -O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n ε -O(k) edges) that achieves a hop diameter that grows like the functional inverse of Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. © 2008 The Author(s). |
Persistent Identifier | http://hdl.handle.net/10722/92638 |
ISSN | 2020 Impact Factor: 0.969 2015 SCImago Journal Rankings: 1.278 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, THH | en_HK |
dc.contributor.author | Gupta, A | en_HK |
dc.date.accessioned | 2010-09-17T10:52:40Z | - |
dc.date.available | 2010-09-17T10:52:40Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | Discrete And Computational Geometry, 2009, v. 41 n. 1, p. 28-44 | en_HK |
dc.identifier.issn | 0179-5376 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/92638 | - |
dc.description.abstract | Given 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 pair of nodes has such a short path that 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 (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog∈ * n+n ε -O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n ε -O(k) edges) that achieves a hop diameter that grows like the functional inverse of Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. © 2008 The Author(s). | en_HK |
dc.language | eng | en_HK |
dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm | en_HK |
dc.relation.ispartof | Discrete and Computational Geometry | en_HK |
dc.subject | Algorithms | en_HK |
dc.subject | Doubling metrics | en_HK |
dc.subject | Hop diameter | en_HK |
dc.subject | Sparse spanners | en_HK |
dc.title | Small hop-diameter sparse spanners for doubling metrics | en_HK |
dc.type | Article | 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.1007/s00454-008-9115-5 | en_HK |
dc.identifier.scopus | eid_2-s2.0-57849150342 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-57849150342&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 41 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 28 | en_HK |
dc.identifier.epage | 44 | en_HK |
dc.identifier.eissn | 1432-0444 | - |
dc.identifier.isi | WOS:000261831500002 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chan, THH=12645073600 | en_HK |
dc.identifier.scopusauthorid | Gupta, A=8354044800 | en_HK |
dc.identifier.citeulike | 3637625 | - |
dc.identifier.issnl | 0179-5376 | - |