The dynamic complexity of transitive closure is in DynTC\(^{0}\).
From MaRDI portal
Publication:1401284
DOI10.1016/S0304-3975(02)00740-5zbMath1045.68154MaRDI QIDQ1401284
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (9)
Dynamic conjunctive queries ⋮ Reachability is in DynFO ⋮ The dynamic descriptive complexity of \(k\)-clique ⋮ Unnamed Item ⋮ Dynamic Complexity of the Dyck Reachability ⋮ Unnamed Item ⋮ On the quantifier-free dynamic complexity of reachability ⋮ A Game Theoretic Approach to the Analysis of Dynamic Networks ⋮ Dynamic complexity of expansion
Cites Work
- Dyn-FO: A parallel, dynamic complexity class
- Incremental and decremental evaluation of transitive closure by first- order queries
- On uniformity within \(NC^ 1\)
- Division in logspace-uniformNC1
- Fast Parallel Arithmetic via Modular Representation
- On Threshold Circuits and Polynomial Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The dynamic complexity of transitive closure is in DynTC\(^{0}\).
