Mantaining dynamic matrices for fully dynamic transitive closure

DOI10.1007/S00453-007-9051-4MaRDI QIDQ930605zbMATH OpenOpenAlexWikidataFDO

Authors Camil Demetrescu, Giuseppe F. Italiano

Publication date 1 July 2008

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0104001

zbMATH Keywords

Transitive closureDynamic graph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

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. 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^{e}psilon)$ time and perform updates in $O(n^{omega(1,epsilon,1)-epsilon}+n^{1+epsilon})$ time, for any $epsilonin[0,1]$, where $omega(1,epsilon,1)$ is the exponent of the multiplication of an $nimes{n}^{epsilon}$ matrix by an $n^{epsilon}imesn$ 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.

Recommendations

• A fully dynamic algorithm for maintaining the transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• An experimental study of algorithms for fully dynamic transitive closure
• Algorithms – ESA 2005
• Dynamic maintenance of the transitive closure in disjunctive graphs
• scientific article; zbMATH DE number 2079364
• A faster and simpler fully dynamic transitive closure
• An experimental study of dynamic algorithms for transitive closure
• Efficient transitive closure of sparse matrices over closed semirings
• scientific article; zbMATH DE number 88951

Cites work

• scientific article; zbMATH DE number 4083002 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• scientific article; zbMATH DE number 2079364 (Why is no real title available?)
• scientific article; zbMATH DE number 3340124 (Why is no real title available?)
• A fully dynamic algorithm for maintaining the transitive closure
• Algorithms – ESA 2004
• Amortized efficiency of a path retrieval data structure
• An On-Line Edge-Deletion Problem
• Computing and Combinatorics
• Efficient determination of the transitive closure of a directed graph
• Finding paths and deleting edges in directed acyclic graphs
• Introduction to algorithms
• Matrix multiplication via arithmetic progressions
• On certificates and lookahead in dynamic graph problems
• On-line computation of transitive closures of graphs
• Speeding up dynamic transitive closure for bounded degree graphs
• Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier

Cited in

(11)

• Decremental SPQR-trees for Planar Graphs
• A fully dynamic algorithm for maintaining the transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Dynamic matrix rank with partial lookahead
• Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n ² barrier
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Dynamic matrix rank with partial lookahead
• Fast dynamic transitive closure with lookahead
• scientific article; zbMATH DE number 2080476 (Why is no real title available?)
• Dynamic Plane Transitive Closure

This page was built for publication: Mantaining dynamic matrices for fully dynamic transitive closure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930605)