The manuscript “Bootstrapping Dynamic Distance Oracles” by Sebastian Forster,  Gramoz Goranci,  Yasamin Nazari, Antonis Skarlatos is now available on  arXiv.

The main new result is a fully dynamic distance oracle for undirected graphs, supporting insertions end deletions of edges, that has arbitrarily small polynomial update and query time and constant stretch. The main technique is a refinement of the widespread reduction idea of obtaining a fully dynamic distance oracle from a “decremental” distance oracle that only supports deletions.