new sparseness results on graph spanners
Let G =( V,E ) be an n -vertex connected graph with positive edge weights. A subgraph G ? = ( V,E ?) is a t-spanner of G if for all u, v &egr; V ,the weighted distance between u and v in G ? is at most t times the weighted distance between u and v in G . We consider the problem of constructing sparse spanners, and the weight , defined as the sum of the edge weights in the spanner. In this paper, we concentrate on constructing spanners of small weight. For an arbitrary positive edge-weighted graph G , for any t > 1, and any &egr;>0, we show that a t -spanner of G with weight O ( n (2+&egr;)/(t-1> )  wt ( MST ) can be constructed in polynomial time. We also show that (log 2 n )-spanners of weight O (log n ) wt ( MST ) can be constructed. We then consider spanners for complete graphs induced by a set of points in d -dimensional real normed space. The weight of an edge xy is the norm of the xy vector. We show that for these graphs, t -spanners with total weight O (log n ) wt ( MST ) can be constructed in polynomial time.
graph spanner posit distance timing paper polynomial log completeness point space vectorization