In the dynamic all-pairs shortest path problem we wish to maintain information about distances in a weighted graph subject to dynamic operations such as edge insertions, edge deletions, and edge weight updates. The most efficient algorithms for this problem maintain a suitable superset of shortest paths in the graph. This superset retains information about the history of previous graph updates so as to avoid pathological situations where algorithms are continuously forced to rebuild large portions of their data structures. On the other hand, the set of maintained paths may grow too large, resulting in both prohibitive space consumption and inefficient updates. To circumvent this problem, the algorithms perform suitable path cleaning operations. In this paper, we implement and experiment with a recent efficient algorithm by Thorup, which differs from the previous algorithms mainly in the way path cleaning is done, and we carry out a thorough experimental investigation on known implementations of dynamic shortest path algorithms. Our experimental study puts the new results into perspective with respect to previous work and gives evidence that path cleaning, although crucial for the theoretical bounds, appears to be instead of very limited impact in practice. © Springer-Verlag Berlin Heidelberg 2006.

Does path cleaning help in dynamic all-pairs shortest paths? / Demetrescu, Camil; P., Faruolo; G. F., Italiano; M., Thorup. - 4168:(2006), pp. 732-743. (Intervento presentato al convegno 14th Annual European Symposium on Algorithms, ESA 2006 tenutosi a Zurich) [10.1007/11841036_65].

Does path cleaning help in dynamic all-pairs shortest paths?

DEMETRESCU, Camil;
2006

Abstract

In the dynamic all-pairs shortest path problem we wish to maintain information about distances in a weighted graph subject to dynamic operations such as edge insertions, edge deletions, and edge weight updates. The most efficient algorithms for this problem maintain a suitable superset of shortest paths in the graph. This superset retains information about the history of previous graph updates so as to avoid pathological situations where algorithms are continuously forced to rebuild large portions of their data structures. On the other hand, the set of maintained paths may grow too large, resulting in both prohibitive space consumption and inefficient updates. To circumvent this problem, the algorithms perform suitable path cleaning operations. In this paper, we implement and experiment with a recent efficient algorithm by Thorup, which differs from the previous algorithms mainly in the way path cleaning is done, and we carry out a thorough experimental investigation on known implementations of dynamic shortest path algorithms. Our experimental study puts the new results into perspective with respect to previous work and gives evidence that path cleaning, although crucial for the theoretical bounds, appears to be instead of very limited impact in practice. © Springer-Verlag Berlin Heidelberg 2006.
2006
14th Annual European Symposium on Algorithms, ESA 2006
algorithms; dynamics; edge deletions
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Does path cleaning help in dynamic all-pairs shortest paths? / Demetrescu, Camil; P., Faruolo; G. F., Italiano; M., Thorup. - 4168:(2006), pp. 732-743. (Intervento presentato al convegno 14th Annual European Symposium on Algorithms, ESA 2006 tenutosi a Zurich) [10.1007/11841036_65].
File allegati a questo prodotto
File Dimensione Formato  
VE_2006_11573-50578.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 309.97 kB
Formato Adobe PDF
309.97 kB Adobe PDF   Contatta l'autore

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/50578
 Attenzione

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

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