An Empirical Criterion for Transitive Closure

Abstract

The paper establishes a simple and computationally economical criterion for determining whether a given adjacency matrix represents a transitive closure or not. The criterion is based on a new iterative method for finding the transitive closure adjacency matrix. This method is equivalent to but computationally more efficient than the traditional Boolean sum of successive powers of the original adjacency matrix to determine the transitive closure matrix. However, it is computationally less efficient than the Warshall algorithm and the recent more advanced algorithms. Nevertheless, in many cases, in which a given matrix is different from the transitive closure, but may not differ much, a few of the proposed looping steps may suffice to find the transitive closure, avoiding the computational burden of the best-in-class algorithms. Thus, the criterion and the recursive relation are apt in complementing the extant methods to establish an efficient evaluation engine for the determination of the transitive closure.