Parallel Realization of the Algorithm of Construction of all Routes in a Graph by Means of Relational Algebra
Abstract
The paper describes a method of optimizing the algorithm for constructing all routes in a graph by means of relational algebra. The problem solved by the proposed method belongs to the class of NP-complete problems. This fact indicates the necessity of finding an effective solution to reduce the computational complexity of this problem. The sequential implementation of the algorithm is based on the method of route construction using the operation (1, 0)-inverted product of multidimensional matrices and is formalized in the concepts of relational algebra. The described algorithm, realized with the use of in memory technology, allows to perform operations directly on the keys of the initial data without preliminary reduction them to matrix form. In consequence of homomorphism of relational algebra and algebra of multidimensional matrices, which has a natural parallelism, there is a possibility to increase the efficiency of the algorithm by distributing data over several processors. The paper gives a proof of isomorphism of both algebras in the framework of the problem. The approach proposed in the article allows to perform parallel computations both on a local machine (allocation of separate threads for fragments of initial data) and to scale them on PCs united in a local network. The time required to construct all possible routes in a graph is chosen as an efficiency indicator of the proposed algorithm. The comparative analysis of sequential and parallel realizations of methods executed on one computer by means of relational database Microsoft SQL Server is given.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
