Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure |
| |
Authors: | Camil Demetrescu Giuseppe F Italiano |
| |
Affiliation: | (1) Dipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”, Rome, Italy;(2) Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Rome, Italy |
| |
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 Ω(n
2) entries of this matrix, no better bounds are possible for this class of algorithms.
This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of
Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving,
Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms
for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented
at the 41st Annual Symp. on Foundations of Computer Science, 2000. |
| |
Keywords: | Dynamic graph algorithms Transitive closure |
本文献已被 SpringerLink 等数据库收录! |
|