Average update times for fully-dynamic all-pairs shortest paths

We study the fully-dynamic all pairs shortest path problem for graphs with arbitrary non-negative edge weights. It is known for digraphs that an update of the distance matrix costs O(n2.75polylog(n)) worst-case time (Thorup, 2005 [20]) and O(n2log3(n)) amortized time (Demetrescu and Italiano, 2004 [4]) where nn is the number of vertices. We present the first average-case analysis of the undirected problem. For a random update we show that the expected time per update is bounded by O(n4/3+ε)O(n4/3+ε) for all ε>0ε>0. If the graph is outside the critical window, we prove even smaller bounds.