Printable PDF
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

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