The dynamic complexity of transitive closure is in DynTC0
- 1 March 2003
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 296 (3) , 473-485
- https://doi.org/10.1016/s0304-3975(02)00740-5
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Division Is In Uniform TC0Published by Springer Nature ,2001
- Division in logspace-uniformNC1RAIRO - Theoretical Informatics and Applications, 2001
- Dynamic tree isomorphism via first-order updates to a relational databasePublished by Association for Computing Machinery (ACM) ,1998
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityPublished by Association for Computing Machinery (ACM) ,1998
- Dyn-FO: A Parallel, Dynamic Complexity ClassJournal of Computer and System Sciences, 1997
- Incremental and Decremental Evaluation of Transitive Closure by First-Order QueriesInformation and Computation, 1995
- On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQLElectronic Workshops in Computing, 1995
- On Threshold Circuits and Polynomial ComputationSIAM Journal on Computing, 1992
- Fast Parallel Arithmetic via Modular RepresentationSIAM Journal on Computing, 1991
- On uniformity within NC1Journal of Computer and System Sciences, 1990