A post-publication acknowledgment: Connection Scheme B was inspired byan additive source-wise spanner due to M. Elkin (unpublished). In his construction, for any set of sources S,
the distances between pairs in S×S
arepreserved to within +2 stretch; the size of the spanner is O(n|S|^{1/2}).
Theorem 4.2generalizes this construction in multiple ways. One consequence is that distances between pairs in S×V can be preserved
to within +O(log n)with the same size spanner. |