CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
JEFFERY S. SALOWE · International Journal of Computational Geometry & Applications · 1991
Given a connected graph G=(V,E) with positive edge weights, define the distance d G (u,v) between vertices u and v to be the length of a shortest path from u to v in G. A spanning subgraph G' of G is said to be a t-spanner for G if, for every pair of vertices u and v, d G' (u,v)≤t·d G (u,v). Consider a complete graph G whose vertex set is a set of n points in [Formula: see text] and whose edge weights are given by the L p distance between respective points. Given input parameter ∊, 0<∊≤1, we show how to construct a (1+∊)-spanner for G containing [Formula: see text] edges in [Formula: see text] time. We apply this spanner to the construction of approximate minimum spanning trees.