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].
展开▼
