Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon }$ Worst-Case Update Time

Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph $G=(V,E)$ with $n$ vertices undergoing both edge insertions and deletions, and an a…