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(n~(2.75))~1 worst-case time [Thorup, STOC '05] and O(n~2) amortized time [Demetrescu and Italiano, J.ACM '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+ε)) for all ε > 0.