Research Article Open Access

An Empirical Criterion for Transitive Closure

Marius Orlowski1
  • 1 Department of Electrical and Computer Engineering, Virginia Polytechnic Institute and State University, Blacksburg, United States

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.

Journal of Computer Science
Volume 18 No. 12, 2022, 1232-1236

DOI: https://doi.org/10.3844/jcssp.2022.1232.1236

Submitted On: 23 March 2022 Published On: 23 December 2022

How to Cite: Orlowski, M. (2022). An Empirical Criterion for Transitive Closure. Journal of Computer Science, 18(12), 1232-1236. https://doi.org/10.3844/jcssp.2022.1232.1236

  • 1,135 Views
  • 638 Downloads
  • 0 Citations

Download

Keywords

  • Transitive Closure
  • Graph Theory
  • Warshall Algorithm
  • Search Algorithms