Weighted Additive Spanners
share
An α-additive spanner of an undirected graph G=(V, E) is a subgraph H such that the distance between any two vertices in G is stretched by no more than an additive factor of α. It is previously known that unweighted graphs have 2-, 4-, and 6-additive spanners containing O(n^3/2), O(n^7/5), and O(n^4/3) edges, respectively. In this paper, we generalize these results to weighted graphs. We consider α=2W, 4W, 6W, where W is the maximum edge weight in G. We first show that every n-node graph has a subsetwise 2W-spanner on O(n |S|^1/2) edges where S ⊆ V and W is a constant. We then show that for every set P with |P| = p vertex demand pairs, there are pairwise 2W- and 4W-spanners on O(np^1/3) and O(np^2/7) edges respectively. We also show that for every set P, there is a 6W-spanner on O(np^1/4) edges where W is a constant. We then show that every graph has additive 2W- and 4W-spanners on O(n^3/2) and O(n^7/5) edges respectively. Finally, we show that every graph has an additive 6W-spanner on O(n^4/3) edges where W is a constant.
READ FULL TEXT