IRIS - Institutional Research Information System
IRIS è il sistema di gestione integrata dei dati della ricerca adottato dalla Luiss Guido Carli. Il Catalogo dei prodotti della ricerca della Luiss raccoglie e rende disponibile, dove possibile nel rispetto del diritto d'autore, la produzione scientifica dei docenti e ricercatori dell'Ateneo. Il Catalogo alimenta inoltre i siti docenti del MIUR.
EnglishWe 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]
| Titolo: | A new approach to dynamic all pairs shortest paths | |
| Autori: | ||
| Data di pubblicazione: | 2004 | |
| Rivista: | ||
| Citazione: | 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] | |
| Handle: | http://hdl.handle.net/11385/199817 | |
| Appare nelle tipologie: | 01.1 - Articolo su rivista (Article) |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| p968-demetrescu.pdf | Versione dell'editore | DRM non definito | Administrator |
Pubblicazioni consigliate
Copyright © 2022