ALCOMFT-TR-02-1

C. Demetrescu and G.F. Italiano
Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths
Rome. Work package 4. January 2002.

Abstract: Let G be a directed graph with n vertices, subject to dynamic updates, and such that each edge weight can assume at most S different arbitrary real values throughout the sequence of updates. We present a new algorithm for maintaining all pairs shortest paths in G in O(S^0.5· n^2.5 log^0.5n) amortized time per update and in O(1) worst-case time per distance query. This improves over previous bounds. We also show how to obtain query/update trade-offs for this problem, by introducing two new families of algorithms. Algorithms in the first family achieve an update bound of \widetildeO(S· k· n²) and a query bound of \widetildeO(n/k), and improve over the best known update bounds for k in the range (n/S)^1/3<= k < (n/S)^1/2. Algorithms in the second family achieve an update bound of \widetildeO(S· k· n²) and a query bound of \widetildeO(n²/k²), and are competitive with the best known update bounds (first family included) for k in the range (n/S)^1/6<= k <(n/S)^1/3.

Postscript file: ALCOMFT-TR-02-1.ps.gz (70 kb).