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.
No takes yet. Share an insight, caveat, or question.
Chandra et al. (1992) studied this question.