Efficient Transitive Closure Algorithms
Yannis Ioannidis
Raghu Ramakrishnan
Date published: 
Published In: 
14th Int’l VLDB Conference, Long Beach, CA, August 1988, pp. 382-394
Conference Article

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 significantly broader class of queries based on one-sided recursions. We analyze these algorithms and compare them to algorithms in the literature. The results indicate that these algorithms, in addition to their ability to deal with queries that re generalizations of transitive closure, also perform very efficiently, in particular, in the context of a dish-based database environment.

Related files: 

MaDgIK 2009-2018