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 present an algorithm for directed acyclic graphs that breaks through the O(n(2)) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can answer queries in O(n(epsilon)) worst-case time and perform updates in O(n(omega(1, epsilon, 1)-epsilon) + n(1+epsilon)) worst-case time, for any epsilon is an element of [0, 1], where omega(1, epsilon, 1) is the exponent of the multiplication of an n x n(epsilon) matrix by an n(epsilon) x n matrix. The current best bounds on omega(1, epsilon, 1) imply an O(n(0.575)) query time and an O(n(1.575)) update time in the worst case. Our subquadratic algorithm is randomized, and has one-sided error. As an application of this result, we show how to solve single-source reachability in O(n(1.575)) time per update and constant time per query.
| Titolo: | Trade-Offs for Fully Dynamic Transitive Closure on DAGs: Breaking Through the O(n2) Barrier | |
| Autori: | ||
| Data di pubblicazione: | 2005 | |
| Rivista: | ||
| Handle: | http://hdl.handle.net/11385/199815 | |
| Appare nelle tipologie: | 01.1 - Articolo su rivista (Article) |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| p147-demetrescu.pdf | Versione dell'editore | DRM non definito | Administrator |
Pubblicazioni consigliate
Copyright © 2021