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(S0.5 · n2.5 log1.5 n) 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 Õ(S · κ · n2) 1 and a query bound of Õ(n/k), and improve over the best known update bounds for κ in the range (n/S)1/3 ≤ κ < (n/S)1/2. Algorithms in the second family achieve an update bound of Õ S · κ · n2 and a query bound of Õ(n2/κ2), and are competitive with the best known update bounds (first family included) for κ in the range (n/S)1/6 ≤ κ < (n/S) 1/3. © 2002 Springer-Verlag Berlin Heidelberg.
Improved bounds and new trade-offs for dynamic all pairs shortest paths / Demetrescu, Camil; Giuseppe F., Italiano. - 2380 LNCS:(2002), pp. 633-643. (Intervento presentato al convegno 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 tenutosi a Malaga nel 8 July 2002 through 13 July 2002) [10.1007/3-540-45465-9_54].
Improved bounds and new trade-offs for dynamic all pairs shortest paths
DEMETRESCU, Camil;
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(S0.5 · n2.5 log1.5 n) 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 Õ(S · κ · n2) 1 and a query bound of Õ(n/k), and improve over the best known update bounds for κ in the range (n/S)1/3 ≤ κ < (n/S)1/2. Algorithms in the second family achieve an update bound of Õ S · κ · n2 and a query bound of Õ(n2/κ2), and are competitive with the best known update bounds (first family included) for κ in the range (n/S)1/6 ≤ κ < (n/S) 1/3. © 2002 Springer-Verlag Berlin Heidelberg.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.