Efficient Transitive Closure Algorithms

We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a signitkantJy broader class of queries based on onesided recursions. We analyze these algorithms and compare them to algorithms in the literature. The resulti indicate that these algorithms, in addition to their ability to deal with queries that am generakations of transitive closure, also perform very efficiently, in particular, in the context of a dish-based database nvironment.