File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-39206-1_27
- Scopus: eid_2-s2.0-84880285745
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: New Doubling Spanners: Better and Simpler
Title | New Doubling Spanners: Better and Simpler |
---|---|
Authors | |
Issue Date | 2013 |
Publisher | Springer 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? |
Abstract | In 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). |
Description | Lecture Notes in Computer Science, vol. 7965 entitled: Automata, languages, and programming : 40th international colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013: proceedings |
Persistent Identifier | http://hdl.handle.net/10722/186490 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | en_US |
dc.contributor.author | Li, M | en_US |
dc.contributor.author | Ning, L | en_US |
dc.contributor.author | Solomon, S | en_US |
dc.date.accessioned | 2013-08-20T12:11:11Z | - |
dc.date.available | 2013-08-20T12:11:11Z | - |
dc.date.issued | 2013 | en_US |
dc.identifier.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 | en_US |
dc.identifier.isbn | 9783642392054 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/186490 | - |
dc.description | Lecture 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.abstract | In 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.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | - |
dc.relation.ispartof | Lecture Notes in Computer Science | en_US |
dc.rights | The original publication is available at www.springerlink.com | - |
dc.title | New Doubling Spanners: Better and Simpler | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | en_US |
dc.identifier.authority | Chan, HTH=rp01312 | en_US |
dc.identifier.doi | 10.1007/978-3-642-39206-1_27 | - |
dc.identifier.scopus | eid_2-s2.0-84880285745 | - |
dc.identifier.hkuros | 219187 | en_US |
dc.identifier.volume | 7965 | - |
dc.identifier.spage | 315 | - |
dc.identifier.epage | 327 | - |
dc.publisher.place | Germany | - |
dc.identifier.issnl | 0302-9743 | - |