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) over tilde (n(2.75))(1) worst-case time [Thorup, STOC '05) and (O) over tilde (n(2)) amortized time [Demetrescu and Italiano, JACM '04] 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(n(4/3+epsilon)) for all epsilon > 0.