TY - GEN
T1 - An optimal dynamic spanner for doubling metric spaces
AU - Gottlieb, Lee Ad
AU - Roditty, Liam
PY - 2008
Y1 - 2008
N2 - A t-spanner is a graph on a set of points S with the following property: Between any pair of points there is a path in the spanner whose total length is at most t times the actual distance between the points. In this paper, we consider points residing in a metric space equipped with doubling dimension λ, and show how to construct a dynamic (1 + ε)-spanner with degree ε-O(λ) in O( log n/εO(λ))update time. When λ and ε are taken as constants, the degree and update times are optimal.
AB - A t-spanner is a graph on a set of points S with the following property: Between any pair of points there is a path in the spanner whose total length is at most t times the actual distance between the points. In this paper, we consider points residing in a metric space equipped with doubling dimension λ, and show how to construct a dynamic (1 + ε)-spanner with degree ε-O(λ) in O( log n/εO(λ))update time. When λ and ε are taken as constants, the degree and update times are optimal.
UR - http://www.scopus.com/inward/record.url?scp=57749184056&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87744-8_40
DO - 10.1007/978-3-540-87744-8_40
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:57749184056
SN - 3540877436
SN - 9783540877431
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 478
EP - 489
BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
T2 - 16th Annual European Symposium on Algorithms, ESA 2008
Y2 - 15 September 2008 through 17 September 2008
ER -