Open Access
American Research Journal of Computer Science and Information Technology
ISSN (Online): 2572-2921
DOI: 10.46568/arjcsit
New Transitive Closure Criterion
Bradley Department of Electrical and Computer Engineering, Virginia Tech, Blacksburg, Virginia 24061, USA.
Marius Orlowski, “New Transitive Closure Criterion”, American Research Journal of Computer Science and
Information Technology, Vol 5, no. 1, 2022, pp. 1-4.
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.
