File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree

TitleSparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
Authors
Issue Date2012
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
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 How to Cite?
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 ⊆ 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
Persistent Identifierhttp://hdl.handle.net/10722/160095
ISBN
ISSN
2013 SCImago Journal Rankings: 0.310
ISI Accession Number ID

 

Author Affiliations
  1. The University of Hong Kong
DC FieldValueLanguage
dc.contributor.authorChan, HTHen_US
dc.contributor.authorLi, Men_US
dc.contributor.authorNing, Len_US
dc.date.accessioned2012-08-16T06:03:09Z-
dc.date.available2012-08-16T06:03:09Z-
dc.date.issued2012en_US
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-193en_US
dc.identifier.isbn9783642315930-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/160095-
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.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.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.titleSparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degreeen_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-31594-7_16-
dc.identifier.scopuseid_2-s2.0-84880263761-
dc.identifier.hkuros202981en_US
dc.identifier.volume7391-
dc.identifier.spage182-
dc.identifier.epage193-
dc.identifier.isiWOS:000342761000016-
dc.publisher.placeGermany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats