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

AbstractWe 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 n 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+ε) for all ε>0. If the graph is outside the critical window, we prove even smaller bounds