The dynamic complexity of transitive closure is in DynTC0

✍ Scribed by William Hesse

• Book ID: 104325698
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 129 KB
• Volume: 296
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00740-5

✦ Synopsis

This paper presents a fully dynamic algorithm for maintaining the transitive closure of a binary relation. All updates and queries can be computed by constant depth threshold circuits of polynomial size (TC 0 circuits). This places dynamic transitive closure in the dynamic complexity class DynTC 0 , and implies that transitive closure can be maintained in database systems that include ÿrst-order update queries and aggregation operators, using a database with size polynomial in the size of the relation.