The dynamic complexity of transitive closure is in DynTC^0

DOI10.1007/3-540-44503-X_16MaRDI QIDQ4473274zbMATH OpenFDO

Authors William Hesse

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1973/19730234.htm

Mathematics Subject Classification ID

Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• A fully dynamic algorithm for maintaining the transitive closure
• A fully dynamic algorithm for maintaining the transitive closure
• Mantaining dynamic matrices for fully dynamic transitive closure
• scientific article; zbMATH DE number 2079364

Cited in

(5)

• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Incremental recomputation in local languages.
• Dynamic maintenance of the transitive closure in disjunctive graphs
• On the quantifier-free dynamic complexity of reachability
• The research of dynamic transitive closure algorithm for complex networks

This page was built for publication: The dynamic complexity of transitive closure is in DynTC\(^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4473274)