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
KeywordsAlgorithms
Doubling metrics
Hop diameter
Sparse spanners
Issue Date2009
PublisherSpringer 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?
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 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 Identifierhttp://hdl.handle.net/10722/92638
ISSN
2015 Impact Factor: 0.816
2015 SCImago Journal Rankings: 1.278
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorGupta, Aen_HK
dc.date.accessioned2010-09-17T10:52:40Z-
dc.date.available2010-09-17T10:52:40Z-
dc.date.issued2009en_HK
dc.identifier.citationDiscrete And Computational Geometry, 2009, v. 41 n. 1, p. 28-44en_HK
dc.identifier.issn0179-5376en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92638-
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 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.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htmen_HK
dc.relation.ispartofDiscrete and Computational Geometryen_HK
dc.subjectAlgorithmsen_HK
dc.subjectDoubling metricsen_HK
dc.subjectHop diameteren_HK
dc.subjectSparse spannersen_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.doi10.1007/s00454-008-9115-5en_HK
dc.identifier.scopuseid_2-s2.0-57849150342en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-57849150342&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume41en_HK
dc.identifier.issue1en_HK
dc.identifier.spage28en_HK
dc.identifier.epage44en_HK
dc.identifier.eissn1432-0444-
dc.identifier.isiWOS:000261831500002-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridGupta, A=8354044800en_HK
dc.identifier.citeulike3637625-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats