Some Method for Constructing Cycles in a Graph

Abstract

The problem of finding cycles in a graph is an integral part of geoinformation, logistic, and navigation information systems. The problems of finding Hamiltonian and Euler cycles, the traveling salesman problem are so important in modern information systems that provide solutions to problems in various subject areas from traditional transport to scientific problems in chemistry and biology that a large number of publications are devoted to this. A modern feature of the tasks of finding cycles in a graph is the need to process large and super-large data (Big Data). Methods that give an exact solution are reduced to algorithms with exponential computational complexity. To reduce complexity, heuristic methods are proposed, for example, genetic algorithms. A multidimensional matrix approach to the processing of large graphs is proposed, focused on constructing all possible cycles, regardless of the method for calculating their properties (for example, cost, Hamiltonianity, and others). This approach provides efficient parallelization of algorithms for constructing all loops and the use of in database technology for constructing all loops, which is possible due to the isomorphism of the algebra of multidimensional matrices and relational algebra for the class of problems under consideration.

Keywords

• directed graphs
• cycles in a graph
• multidimensional matrices
• databases
• parallel programming