New sparseness results on graph spanners
Barun Chandra, Gautam Das, Giri Narasimhan, José Soares · 1992
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 ε 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.