# Diameter spanners

### Wednesday, June 12th, 2019, 16:10

### Schreiber 309

### Diameter spanners

### Omer Gold, TAU

### Abstract:

The diameter of a graph is one if its most important parameters, being used in many real-word applications. In particular, the diameter dictates how fast information can spread throughout data and communication networks. Designing such networks with a sparse (subquadratic) set of edges and small diameter is highly desired.

Thus, it is a natural question to ask how much can we sparsify a graph while guaranteeing that its diameter is preserved within an approximation factor $t$, for some $t>1$.

To tackle this question, we initiate the study of diameter spanners. Given a directed graph $G = (V, E)$, a subgraph $H = (V, E' \subseteq E)$ is defined to be a $t$-diameter spanner if the diameter of $H$ is at most $t$ times the diameter of $G$.

We show the existence of (and algorithms to compute) various $t$-diameter spanners with a sparse set of edges and $t<2$, for directed unweighted graphs.

We also give diameter spanner constructions for directed graphs with edge-weights that are at least $1$.

Joint work with Keerti Choudhary