Mantaining dynamic matrices for fully dynamic transitive closure

DOI10.1007/S00453-007-9051-4zbMATH Open1147.68090arXivcs/0104001OpenAlexW2118914279WikidataQ61609547 ScholiaQ61609547MaRDI QIDQ930605FDOQ930605

Authors: Camil Demetrescu, Giuseppe F. Italiano 

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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 Keywords

Transitive closureDynamic graph algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Fast dynamic transitive closure with lookahead
• Decremental SPQR-trees for Planar Graphs
• 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
• Title not available (Why is that?)
• A fully dynamic algorithm for maintaining the transitive closure
• 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)