Report Number: CS-TR-75-508
Institution: Stanford University, Department of Computer Science
Title: On computing the transitive closure of a relation.
Author: Eve, James
Date: September 1975
Abstract: An algorithm is presented for computing the transitive closure of an arbitrary relation which is based upon a variant of Tarjan's algorithm [1972] for finding the strongly connected components of a directed graph. This variant leads to a more compact statement of Tarjan's algorithm. If V is the number of vertices in the directed graph representing the relation then the worst case behavior of the proposed algorithm involves O($V^3$) operations. In this respect it is inferior to existing algorithms which require O($V^3$/log V) and O($V^{{log}_2 7}$ log V) operations respectively. The best case behavior involves only O($V^2$) operations.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/508/CS-TR-75-508.pdf