An Optimal Dynamic Spanner for Doubling Metric Spaces
Lists
Only you see this
Abstract
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(\frac{\log n}{\varepsilon^{O(\lambda)}})$ update time. When λ and ε are taken as constants, the degree and update times are optimal.
BibTeX
@inproceedings{gottlieb2008optimal,
author = {Lee-Ad Gottlieb and Liam Roditty},
title = {{An Optimal Dynamic Spanner for Doubling Metric Spaces}},
booktitle = {ESA},
year = {2008},
doi = {10.1007/978-3-540-87744-8\_40},
}Loading related content...