On computing the transitive closure of a relation.

[摘要] 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.

[学科分类] 计算机科学（综合）