Speaker: Adi Gottlieb, NYU
Title: Optimal Dynamic Spanners
Abstract:
A spanner of a graph G is a graph H whose vertex set is the same as that of G but which has fewer edges. The
stretch of H is the maximum of the ratio of the distance between two points a,b in G and their distance in H,
over all points.
We show how to dynamically maintain spanners with low stretch and constant degree in logarithmic time, for
points residing in a space equipped with constant doubling dimension.
This is joint work with Liam Roditty.