Open AccessFast Algorithm for Calculating Transitive Closures of Binary Relations in the Structure of a Network Object
Author(s) -
Vladimir Batsamut,
Sviatoslav Manzura,
Oleksandr Kosiak,
Viacheslav Garmash,
Dmytro Kukharets
Publication year - 2021
Publication title -
computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.184
H-Index - 11
eISSN - 2312-5381
pISSN - 1727-6209
DOI - 10.47839/ijc.20.4.2444
Subject(s) - adjacency matrix , algorithm , tree traversal , computer science , transitive relation , transitive reduction , logical matrix , object (grammar) , adjacency list , matrix (chemical analysis) , data structure , floyd–warshall algorithm , binary number , theoretical computer science , mathematics , dijkstra's algorithm , shortest path problem , group (periodic table) , combinatorics , graph , chemistry , materials science , arithmetic , organic chemistry , voltage graph , line graph , artificial intelligence , composite material , programming language
The article proposes a fast algorithm for constructing the transitive closures between all pairs of nodes in the structure of a network object, which can have both directional and non-directional links. The algorithm is based on the disjunctive addition of the elements of certain rows of the adjacency matrix, which models (describe) the structure of the original network object. The article formulates and proves a theorem that using such a procedure, the matrix of transitive closures of a network object can be obtained from the adjacency matrix in two iterations (traversal) on such an array. An estimate of the asymptotic computational complexity of the proposed algorithm is substantiated. The article presents the results of an experimental study of the execution time of such an algorithm on network structures of different dimensions and with different connection densities. For this indicator, the developed algorithm is compared with the well-known approaches of Bellman, Warshall-Floyd, Shimbel, which can also be used to determine the transitive closures of binary relations of network objects. The corresponding graphs of the obtained dependences are given. The proposed algorithm (the logic embedded in it) can become the basis for solving problems of monitoring the connectivity of various subscribers in data transmission networks in real time when managing the load in such networks, where the time spent on routing information flows directly depends on the execution time of control algorithms, as well as when solving other problems on the network structures.