Low distortion spanners
ACM Transactions on Algorithms · 2009-12 · 6 (1) · 1-22
DOI: 10.1145/1644015.1644022 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 28.12.2009. Verfasst von Seth Pettie. Die Arbeit wurde bisher 45-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Division of Computing and Communication Foundations.
Abstract (Originalsprache)
A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an f -spanner of G if any two vertices u , v at distance d in G are at distance at most f ( d ) in H . There is clearly some trade-off between the sparsity of H and the distortion function f , though the nature of the optimal trade-off is still poorly understood. In this article we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called connection schemes . By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. [1999] and Baswana et al. [2009], and give spanners whose multiplicative distortion quickly tends toward 1. Our results rival the simplicity of all previous algorithms and provide substantial improvements (up to a doubly exponential reduction in edge density) over the comparable spanners of Elkin and Peleg [2004] and Thorup and Zwick [2006].
Förderung
- Division of Computing and Communication Foundations
Zitieren
APA
Pettie, S. (2009). Low distortion spanners. ACM Transactions on Algorithms, 6(1), 1-22. https://doi.org/10.1145/1644015.1644022
Vancouver
Pettie S. Low distortion spanners. ACM Transactions on Algorithms. 2009;6(1):1-22. doi:10.1145/1644015.1644022
BibTeX
@article{Pettie2009,
author = {Pettie, Seth},
title = {Low distortion spanners},
journal = {ACM Transactions on Algorithms},
year = {2009},
volume = {6},
number = {1},
pages = {1--22},
doi = {10.1145/1644015.1644022}
}
EUVIMED