A post-publication acknowledgment: Connection Scheme B was inspired by an 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 are preserved to within +2 stretch; the size of the spanner is O(n|S|1/2). Theorem 4.2 generalizes 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. |