Sparse distance preservers and additive spanners

Abstract

A notion of distance preserving approach, briefly, a preserver, is introduced. It is shown that any graph has a subgraph D-preserver with at most O(n2/D) edges, and there are graphs and diagraphs for which any undirected Steiner D-preserver contains Ω(n2/D) edges. However, it is illustrated that if one allows a directed Steiner D-preserver, then these bounds can be improved.