پیوندهای مفید
آمار
| تعداد نشریات | 31 |
| تعداد شمارهها | 484 |
| تعداد مقالات | 4,286 |
| تعداد مشاهده مقاله | 7,298,689 |
| تعداد دریافت فایل اصل مقاله | 4,896,197 |
Set-theoretic form of Warshall's algorithm for computing transitive closure of a binary relation | ||
| Journal of Hyperstructures | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 30 خرداد 1405 اصل مقاله (1.69 M) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22098/jhs.2026.17764.1106 | ||
| نویسندگان | ||
| Aboutorab Pourhaghani؛ Seid Mohammad 09131538101 Anvariyeh* | ||
| Department of Mathematical Sciences, Yazd University, Yazd, Iran | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Binary relation؛ Transitive closure؛ Warshall's Algorithm | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 30 تعداد دریافت فایل اصل مقاله: 11 |
||