Computer Science – Data Structures and Algorithms
Scientific paper
2001-03-31
Computer Science
Data Structures and Algorithms
52 pages, 5 figures
Scientific paper
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. Our matrix-based approach yields an algorithm for directed acyclic graphs that breaks through the $O(n^2)$ barrier on the single-operation complexity of fully dynamic transitive closure. We can answer queries in $O(n^\epsilon)$ time and perform updates in $O(n^{\omega(1,\epsilon,1)-\epsilon}+n^{1+\epsilon})$ time, for any $\epsilon\in[0,1]$, where $\omega(1,\epsilon,1)$ is the exponent of the multiplication of an $n\times n^{\epsilon}$ matrix by an $n^{\epsilon}\times n$ matrix. The current best bounds on $\omega(1,\epsilon,1)$ imply an $O(n^{0.58})$ query time and an $O(n^{1.58})$ update time. Our subquadratic algorithm is randomized, and has one-side error.
Demetrescu Camil
Italiano Giuseppe F.
No associations
LandOfFree
Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-406306