A fully dynamic algorithm for maintaining the transitive closure
From MaRDI portal
Publication:5917499
DOI10.1006/jcss.2002.1883zbMath1020.68106OpenAlexW3139713485MaRDI QIDQ5917499
Publication date: 4 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/640bccbd7d74d579bb6df7a11f71b3e2f920b844
Related Items (8)
Fast dynamic transitive closure with lookahead ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ A Game Theoretic Approach to the Analysis of Dynamic Networks
Cites Work
- 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
- Fast rectangular matrix multiplication and applications
- Lower bounds for fully dynamic connectivity problems in graphs
- Speeding up dynamic transitive closure for bounded degree graphs
- Complexity models for incremental computation
- Size-estimation framework with applications to transitive closure and reachability
- On certificates and lookahead in dynamic graph problems
- Gaussian elimination is not optimal
- An On-Line Edge-Deletion Problem
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: A fully dynamic algorithm for maintaining the transitive closure
