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.
2002
9783540438649
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/50509
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
social impact