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