Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

The Dynamic Complexity of Transitive Closure Is in DynTC°

William HesseContact Information

(6)  Department of Computer Science, University of Massachusetts, MA 01002 Amherst
Abstract
This paper presents a fully dynamic algorithm for maintaining the transitive closure of a directed graph. All updates and queries can be computed by constant depth threshold circuits of polynomial size (TC° circuits). This places transitive closure in the dynamic complexity class DynTC°, and implies that transitive closure can be maintained in databases using updates written in a first order query language plus counting operators, while keeping the size of the database polynomial in the size of the graph.

Contact Information William Hesse
Email: whesse@cs.umass.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)