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.