Additive graph spanners

A spanning subgraph S = (V, E′) of a connected simple graph G = (V, E) is a f(x)-spanner if for any pair of nodes u and v, dS(u, v) ≦ f(dG(u, v)), where dG and dS are the usual distance functions in graphs G and S, respectively. We are primarily interested in (t + x)-spanners, which we refer to as additive spanners. We construct low-degree additive spanners for X-trees, pyramids, and multidimensional grids. We prove, for arbitrary t > 0, that to determine whether a given graph G has an additive spanner with no more than m edges is NP-complete. © 1993 by John Wiley & Sons, Inc.