File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
  • Basic View
  • Metadata View
  • XML View
TitleSparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
 
AuthorsChan, HTH
Li, M1
Ning, L1
 
Issue Date2012
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationThe 39th International Colloquium (ICALP 2012), Warwick, United Kingdom, 9-13 July 2012. In Lecture Notes in Computer Science, 2012, v. 7391, p. 182-193 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-31594-7_16
 
AbstractWe study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k,t)-VFTS or simply k-VFTS), if for any subset S ⊆ X with |S| ≤ k, it holds that d H ∖ S (x, y) ≤ t ·d(x, y), for any pair of x, y ∈ X ∖ S. For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m ≥ 2n, we can reduce the hop-diameter of the above k-VFTS to O(α(m, n)) by adding O(km) edges, where α is a functional inverse of the Ackermann’s function. Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k 2 n) edges and maximum degree O(k 2).
 
DescriptionSession A6
Lecture Notes in Computer Science, Vol. 7391 entitled: Automata, Languages, and Programming: 39th international colloquium, ICALP 2012, Warwick, UK, 9-13 July 2012: Proceedings
 
ISBN9783642315930
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-31594-7_16
 
ISI Accession Number IDWOS:000342761000016
 
DC FieldValue
dc.contributor.authorChan, HTH
 
dc.contributor.authorLi, M
 
dc.contributor.authorNing, L
 
dc.date.accessioned2012-08-16T06:03:09Z
 
dc.date.available2012-08-16T06:03:09Z
 
dc.date.issued2012
 
dc.description.abstractWe study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k,t)-VFTS or simply k-VFTS), if for any subset S ⊆ X with |S| ≤ k, it holds that d H ∖ S (x, y) ≤ t ·d(x, y), for any pair of x, y ∈ X ∖ S. For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m ≥ 2n, we can reduce the hop-diameter of the above k-VFTS to O(α(m, n)) by adding O(km) edges, where α is a functional inverse of the Ackermann’s function. Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k 2 n) edges and maximum degree O(k 2).
 
dc.descriptionSession A6
 
dc.descriptionLecture Notes in Computer Science, Vol. 7391 entitled: Automata, Languages, and Programming: 39th international colloquium, ICALP 2012, Warwick, UK, 9-13 July 2012: Proceedings
 
dc.identifier.citationThe 39th International Colloquium (ICALP 2012), Warwick, United Kingdom, 9-13 July 2012. In Lecture Notes in Computer Science, 2012, v. 7391, p. 182-193 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-31594-7_16
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-31594-7_16
 
dc.identifier.epage193
 
dc.identifier.hkuros202981
 
dc.identifier.isbn9783642315930
 
dc.identifier.isiWOS:000342761000016
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-84880263761
 
dc.identifier.spage182
 
dc.identifier.urihttp://hdl.handle.net/10722/160095
 
dc.identifier.volume7391
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.titleSparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, HTH</contributor.author>
<contributor.author>Li, M</contributor.author>
<contributor.author>Ning, L</contributor.author>
<date.accessioned>2012-08-16T06:03:09Z</date.accessioned>
<date.available>2012-08-16T06:03:09Z</date.available>
<date.issued>2012</date.issued>
<identifier.citation>The 39th International Colloquium (ICALP 2012), Warwick, United Kingdom, 9-13 July 2012. In Lecture Notes in Computer Science, 2012, v. 7391, p. 182-193</identifier.citation>
<identifier.isbn>9783642315930</identifier.isbn>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/160095</identifier.uri>
<description>Session A6</description>
<description>Lecture Notes in Computer Science, Vol. 7391 entitled: Automata, Languages, and Programming: 39th international colloquium, ICALP 2012, Warwick, UK, 9-13 July 2012: Proceedings</description>
<description.abstract>We study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k,t)-VFTS or simply k-VFTS), if for any subset S&#8201;&#8838;&#8201;X with |S|&#8201;&#8804;&#8201;k, it holds that d H&#8201;&#8726;&#8201;S (x, y)&#8201;&#8804;&#8201;t &#183;d(x, y), for any pair of x, y&#8201;&#8712;&#8201;X&#8201;&#8726;&#8201;S.
For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. In addition, we also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m&#8201;&#8805;&#8201;2n, we can reduce the hop-diameter of the above k-VFTS to O(&#945;(m, n)) by adding O(km) edges, where &#945; is a functional inverse of the Ackermann&#8217;s function.
Finally, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k 2 n) edges and maximum degree O(k 2).</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<title>Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree</title>
<type>Conference_Paper</type>
<identifier.doi>10.1007/978-3-642-31594-7_16</identifier.doi>
<identifier.scopus>eid_2-s2.0-84880263761</identifier.scopus>
<identifier.hkuros>202981</identifier.hkuros>
<identifier.volume>7391</identifier.volume>
<identifier.spage>182</identifier.spage>
<identifier.epage>193</identifier.epage>
<identifier.isi>WOS:000342761000016</identifier.isi>
<publisher.place>Germany</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong