printable pdf
比利时vs摩洛哥足彩 ,
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

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