##### Department of Mathematics,

University of California San Diego

****************************

### Spectral Graph Theory

## Sam Spiro

#### UCSD

## Additive Spanners

##### Abstract:

An $(\alpha,\beta)$-spanner of a graph G is a subgraph H that distorts distances in G up to a multiplicative factor of $\alpha$ and an additive factor of $\beta$, where the goal is to construct an H with as few edges as possible. When $\beta=0$ we call H a multiplicative spanner, and when $\alpha=1$ we call H an additive spanner. It is known how to construct multiplicative spanners of essentially optimal size, but much less is known about additive spanners. In this talk we discuss a recent result which shows how to construct a (0,6)-additive spanner for any graph G.

### October 16, 2018

### 2:00 PM

### AP&M 7321

****************************