American Research Journal of Computer Science and Information Technology

Novel recursive matrix algorithm for the transitive closure is proposed that is computationally more efficient than the closure theorem O(n4) and runs only slightly longer in time O(n3ln2 (n)) than the Warshall algorithm O(n3). However, the proposed algorithm can be combined with advanced, extant algorithms by Chan, Zwick, and Margalit to further improve its bit operation performance. From the recursive matrix algorithm a simple criterium can be derived to ascertain whether some given adjacency matrix of a graph with n nodes already represents a transitive closure. If the criterium is met, the calculation of the transitive closure by any other algorithm can, obviously, be eschewed.