File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: New Doubling Spanners: Better and Simpler

TitleNew Doubling Spanners: Better and Simpler
Authors
Issue Date2013
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 40th International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia, 8-12 July 2013. In Lecture Notes in Computer Science, 2013, v. 7965, p. 315-327 How to Cite?
AbstractIn a seminal STOC’95 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter O(logn) and lightness O(logn) (i.e., weight (O(log n) cdot w( extsf{MST}))) can be constructed in O(n logn) time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC’13 (even for doubling metrics). In this work we present a simpler construction of spanners for doubling metrics with the above guarantees. Moreover, our construction extends in a simple and natural way to provide k-fault tolerant spanners with maximum degree O(k 2), hop-diameter O(logn) and lightness O(k 2 logn).
DescriptionLecture Notes in Computer Science, vol. 7965 entitled: Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013: proceedings
Persistent Identifierhttp://hdl.handle.net/10722/186490
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorChan, HTHen_US
dc.contributor.authorLi, Men_US
dc.contributor.authorNing, Len_US
dc.contributor.authorSolomon, Sen_US
dc.date.accessioned2013-08-20T12:11:11Z-
dc.date.available2013-08-20T12:11:11Z-
dc.date.issued2013en_US
dc.identifier.citationThe 40th International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia, 8-12 July 2013. In Lecture Notes in Computer Science, 2013, v. 7965, p. 315-327en_US
dc.identifier.isbn9783642392054-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/186490-
dc.descriptionLecture Notes in Computer Science, vol. 7965 entitled: Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013: proceedings-
dc.description.abstractIn a seminal STOC’95 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter O(logn) and lightness O(logn) (i.e., weight (O(log n) cdot w( extsf{MST}))) can be constructed in O(n logn) time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC’13 (even for doubling metrics). In this work we present a simpler construction of spanners for doubling metrics with the above guarantees. Moreover, our construction extends in a simple and natural way to provide k-fault tolerant spanners with maximum degree O(k 2), hop-diameter O(logn) and lightness O(k 2 logn).-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleNew Doubling Spanners: Better and Simpleren_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HTH: hubert@cs.hku.hken_US
dc.identifier.authorityChan, HTH=rp01312en_US
dc.identifier.doi10.1007/978-3-642-39206-1_27-
dc.identifier.scopuseid_2-s2.0-84880285745-
dc.identifier.hkuros219187en_US
dc.identifier.volume7965-
dc.identifier.spage315-
dc.identifier.epage327-
dc.publisher.placeGermany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats