Pairwise spanners

We consider the problem of computing a sparse subgraph H of G such that for
every pair (u,v) in P, the u-v distance in H is at most the u-v
distance in G + t,
for some small t. Such a subgraph is called a (1,t) pairwise spanner. When
P = S x V for some subset S of V, we call it a sourcewise spanner.

We show the construction of a sparse (1,2) sourcewise spanner and show a simple
deterministic construction of a (1,4) all-pairs spanner using this
sourcewise spanner.
We then show efficient algorithms to compute sparse (1,t) pairwise spanners and
(1,t) sourcewise spanners for any integer t \ge 1. A D-spanner is a
subgraph of G where
distances at least D are approximately preserved. We also show how to construct
certain sparse (1,t) D-spanners.

(Joint work with Marek Cygan, Fabrizio Grandoni, and Nithin Varma)