Set-theoretic form of Warshall's algorithm for computing transitive closure of a binary relation

Articles in Press

Document Type : Research Paper

Authors

Department of Mathematical Sciences, Yazd University, Yazd, Iran

Abstract

In this paper, we investigate about the transitive closure of a binary relation. We present the algorithms for computing the transitive closure in matrix form and set-theoretic form, as well as their complexity. First, we recall a simple algorithm (Algorithm \ref{transitivematrixalgorithm}) and the Warshall's algorithm(Algorithm \ref{warshallmatrixalgorithm}), along with their complexity, to obtain the matrix of transitive closure. Then, we introduce the Algorithm \ref{transitiverelationalgorithm} and Warshall's algorithm (Algorithm \ref{warshallsetalgorithm}) in set-theoretic form, instead of matrix form, as well their complexity. Finally, the Maple codes of the newly introduced algorithms are provided along with an example of how to use them in Maple.

Keywords

Main Subjects

References

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, fourth edition. MIT Press, 2022.
[2] E. Nuutila. Efficient transitive closure computation in large digraphs. Acta Polytechnica Scandinavia: Math. Comput. Eng., 74(1995), 1–124.
[3] S. Pemmaraju and S. Skiena. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica ®. Cambridge University Press, 2003.
[4] A. Pourhaghani, S. M. Anvariyeh, and B. Davvaz. An algorithm to calculate the members of the relation β in hypergroupoids. Journal of Algebraic Hyperstructures and Logical Algebras, 5(2)(2024), 137–152.
[5] K. H. Rosen. Handbook of Discrete and Combinatorial Mathematics, Second Edition. Chapman and Hall/CRC, 2018.
[6] K. H. Rosen. Discrete Mathematics and Its Applications. McGraw Hill, 8th edition, 2019.
[7] B. Roy. Transitivit´e et connexit´e. C. R. Acad. Sci. Paris, 249(1959), 216–218.
[8] S. S. Skiena. The Algorithm Design Manual. Springer International Publishing, 2020.
[9] S. Warshall. A theorem on boolean matrices. Journal of the ACM, 9(1)(1962), 11–12.
[10] E. W. Weisstein. Floyd-warshall algorithm. Wolfram Research, Inc., (2008), 1.
Journal of Hyperstructures

Articles in Press, Accepted Manuscript
Available Online from 20 June 2026

Files

Share

How to cite

Statistics