EUVIMEDEUVIMED entdecken
Crossref

Low distortion spanners

Seth Pettie

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →