We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2 log3 n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.

A new approach to dynamic all pairs shortest paths / C., Demetrescu; Italiano, Giuseppe Francesco. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - 51:6(2004), pp. 968-992. [10.1145/1039488.1039492]

A new approach to dynamic all pairs shortest paths

ITALIANO G
2004

Abstract

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2 log3 n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.
2004
Design and Analysis of Algorithms; Shortest Path Algorithms; Dynamic Data Structures
A new approach to dynamic all pairs shortest paths / C., Demetrescu; Italiano, Giuseppe Francesco. - In: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY. - ISSN 0004-5411. - 51:6(2004), pp. 968-992. [10.1145/1039488.1039492]
File in questo prodotto:
File Dimensione Formato  
p968-demetrescu.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 345.91 kB
Formato Adobe PDF
345.91 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

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/11385/199817
Citazioni
  • Scopus 205
  • ???jsp.display-item.citation.isi??? 149
social impact