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

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