Open Access
American Research Journal of Computer Science and Information Technology
ISSN (Online): 2572-2921
DOI: 10.46568/arjcsit
New Transitive Closure Criterion
Abstract
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.
