We 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.

Demetrescu, C., Italiano, G.f. (2005). Trade-offs for fully dynamic transitive closure on DAGs: Breaking through the O(n(2)) barrier. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 52(2), 147-156 [10.1145/1059513.1059514].

Trade-offs for fully dynamic transitive closure on DAGs: Breaking through the O(n(2)) barrier

ITALIANO, GIUSEPPE FRANCESCO
2005-01-01

Abstract

We 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.
2005
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Con Impact Factor ISI
Dynamic graph algorithms; Transitive closure
Demetrescu, C., Italiano, G.f. (2005). Trade-offs for fully dynamic transitive closure on DAGs: Breaking through the O(n(2)) barrier. JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY, 52(2), 147-156 [10.1145/1059513.1059514].
Demetrescu, C; Italiano, Gf
Articolo su rivista
File in 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/2108/38528
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 26
social impact