Mantaining dynamic matrices for fully dynamic transitive closure

DOI10.1007/s00453-007-9051-4zbMath1147.68090arXivcs/0104001OpenAlexW2118914279WikidataQ61609547 ScholiaQ61609547MaRDI QIDQ930605

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

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

Related Items

Decremental SPQR-trees for Planar Graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier

Cites Work

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