This survey provides a guiding reference to researchers seeking an overview of the large
body of literature about graph spanners. It surveys the current literature covering various …

The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up
to a multiplicative factor of α and an additive term β. It is well known that any graph contains …

We introduce and study the notions of pairwise and sourcewise preservers. Given an
undirected N-vertex graph G=(V, E) and a set P of pairs of vertices, let G'=(V, H), H ⊆ E, be …

We study the s-sources almost shortest paths (abbreviated s-ASP) problem. Given an
unweighted graph G=(V, E), and a subset S⊆ V of s nodes, the goal is to compute almost …

Given a directed graph G=(V,E) and an integer k≧1, a k-transitive-closure-spanner (k-TC-
spanner) of G is a directed graph H=(V,E_H) that has (1) the same transitive-closure as G …

This paper considers additive and purely additive spanners. We present a new purely
additive spanner of size Õ (n 7/5) with additive stretch 4. This construction fills in the gap …

Spanner of an undirected graph G=(V, E) is a subgraph that is sparse and yet preserves all-
pairs distances approximately. More formally, a spanner with stretch t∈ ℕ is a subgraph (V …

For an unweighted undirected graph G=(V, E), and a pair of positive integers α≥ 1, β≥ 0, a
subgraph G'=(V, H), H⊆ E, is called an (α, β)-spanner of G if for every pair of vertices u, v∈ …

Abstract An (α, β)-spanner of an unweighted graph G is a subgraph H that approximates
distances in G in the following sense. For any two vertices u, v: δH (u, v)≤ αδG (u, v)+ β …