In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n(2)) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Omega(n(2)) entries of this matrix, no better bounds are possible for this class of algorithms.

Demetrescu, C., & Italiano, G.F. (2008). Mantaining dynamic matrices for fully dynamic transitive closure. ALGORITHMICA, 51(4), 387-427 [10.1007/s00453-007-9051-4].

Mantaining dynamic matrices for fully dynamic transitive closure

ITALIANO, GIUSEPPE FRANCESCO
2008

Abstract

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n(2)) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Omega(n(2)) entries of this matrix, no better bounds are possible for this class of algorithms.
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. (2008). Mantaining dynamic matrices for fully dynamic transitive closure. ALGORITHMICA, 51(4), 387-427 [10.1007/s00453-007-9051-4].
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: http://hdl.handle.net/2108/38565
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 7
social impact