File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: New Doubling Spanners: Better and Simpler

TitleNew Doubling Spanners: Better and Simpler
Authors
KeywordsArya et al. Stoc 1995 conjecture
Fault-tolerant doubling spanners
Lightness
Optimal hop-diameter
Small degree
Issue Date2015
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
SIAM Journal on Computing, 2015, v. 44 n. 1, p. 37-53 How to Cite?
AbstractIn a seminal STOC 1995 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter $O(log n)$, and lightness $O(log n)$ (i.e., weight $O(log n) cdot w({MST}))$ can be constructed in $O(n log n)$ time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC 2013. In fact, Elkin and Solomon proved that the conjecture of Arya et al. holds even in doubling metrics. However, Elkin and Solomon's spanner construction is complicated. In this work we present a significantly simpler construction of spanners for doubling metrics with the same guarantees as above. Our construction is based on the basic net-tree spanner framework. However, by employing well-known properties of the net-tree spanner in conjunction with numerous new ideas, we managed to get significantly stronger results. First and foremost, our construction extends in a simple and natural way to provide $k$-fault tolerant spanners with maximum degree $O(k^2)$, hop-diameter $O(log n)$, and lightness $O(k^2 log n)$. This is the first construction of fault-tolerant spanners (even for Euclidean metrics) that achieves good bounds (polylogarithmic in $n$ and polynomial in $k$) on all the involved parameters simultaneously. Second, we show that the lightness bound of our construction can be improved to $O(k^2)$ (with high probability), for random points in $[0,1]^D$, where $2 le D = O(1)$. © 2015, Society for Industrial and Applied Mathematics
Persistent Identifierhttp://hdl.handle.net/10722/215509
ISSN
2017 Impact Factor: 0.902
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChan, THH-
dc.contributor.authorLi, M-
dc.contributor.authorNing, L-
dc.contributor.authorSolomon, S-
dc.date.accessioned2015-08-21T13:28:28Z-
dc.date.available2015-08-21T13:28:28Z-
dc.date.issued2015-
dc.identifier.citationSIAM Journal on Computing, 2015, v. 44 n. 1, p. 37-53-
dc.identifier.issn0097-5397-
dc.identifier.urihttp://hdl.handle.net/10722/215509-
dc.description.abstractIn a seminal STOC 1995 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter $O(log n)$, and lightness $O(log n)$ (i.e., weight $O(log n) cdot w({MST}))$ can be constructed in $O(n log n)$ time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC 2013. In fact, Elkin and Solomon proved that the conjecture of Arya et al. holds even in doubling metrics. However, Elkin and Solomon's spanner construction is complicated. In this work we present a significantly simpler construction of spanners for doubling metrics with the same guarantees as above. Our construction is based on the basic net-tree spanner framework. However, by employing well-known properties of the net-tree spanner in conjunction with numerous new ideas, we managed to get significantly stronger results. First and foremost, our construction extends in a simple and natural way to provide $k$-fault tolerant spanners with maximum degree $O(k^2)$, hop-diameter $O(log n)$, and lightness $O(k^2 log n)$. This is the first construction of fault-tolerant spanners (even for Euclidean metrics) that achieves good bounds (polylogarithmic in $n$ and polynomial in $k$) on all the involved parameters simultaneously. Second, we show that the lightness bound of our construction can be improved to $O(k^2)$ (with high probability), for random points in $[0,1]^D$, where $2 le D = O(1)$. © 2015, Society for Industrial and Applied Mathematics-
dc.languageeng-
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computing-
dc.rights© 2015 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 44, issue 1, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectArya et al. Stoc 1995 conjecture-
dc.subjectFault-tolerant doubling spanners-
dc.subjectLightness-
dc.subjectOptimal hop-diameter-
dc.subjectSmall degree-
dc.titleNew Doubling Spanners: Better and Simpler-
dc.typeArticle-
dc.identifier.emailChan, THH: hubert@cs.hku.hk-
dc.identifier.authorityChan, THH=rp01312-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/130930984-
dc.identifier.scopuseid_2-s2.0-84923767323-
dc.identifier.hkuros247361-
dc.identifier.volume44-
dc.identifier.issue1-
dc.identifier.spage37-
dc.identifier.epage53-
dc.identifier.isiWOS:000353967100002-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats