Conference paper
Sparse distance preservers and additive spanners
Béla Bollobás, Don Coppersmith, et al.
SODA 1998
We define the subvariance S℘(ℱ) of a family of graphs ℱ with respect to property ℱ to be the infimum of the ratio |H1|/|H2|, where H1 and H2 are any two maximal spanning subgraphs of G with property ℘, and where G is a member of ℱ. It is shown that, for the family of all connected graphs, the subvariance when ℘ is planar, outerplanar, and bipartite planar, is 1/2, 1/2, and 1/2, respectively.
Béla Bollobás, Don Coppersmith, et al.
SODA 1998
Don Coppersmith, Uriel Feige, et al.
SIAM Journal on Discrete Mathematics
Don Coppersmith, James B. Shearer
Electronic Journal of Combinatorics
Roy L. Adler, Don Coppersmith, et al.
IEEE Trans. Inf. Theory