Prof. Michael Elkin

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(n²/D) edges, and there are graphs and diagraphs for which any undirected Steiner D-preserver contains Ω(n²/D) edges. However, it is illustrated that if one allows a directed Steiner D-preserver, then these bounds can be improved.