EVALUATION OF THE COMPLEXITY OF ALGORITHMS IMPLEMENTING OPERATIONS ON METAGRAPHS

Goryachkin Boris Sergeevich, Gapanyuk Yuri Evgenievich, Vinnikov Stepan Sergeevich

Problem statement. Currently, algorithms for performing operations on metagraphs have not been described or implemented, which limits the possibilities for processing such structures. Goal. Provide an opportunity to work with metagraphs on a mathematical and algorithmic level. Results. An alternative description of the metagraphic model has been considered, and its significant differences from the classical model have been indicated. Mathematical operations on metagraphs have been described. Algorithms that implement these operations have been given. A theoretical assessment of the complexity of such algorithms has been given. A program that implements these algorithms has been written, and its operability has been tested. Experiments with calculations on metagraphs of different sizes have been carried out. A comparison of theoretical and experimental data has been carried out, and the theoretical assessment has been confirmed. Practical significance. The transition from the classical description of metagraphs to the new one made it possible to conveniently and concisely describe operations on metagraphs, and also simplified work with this structure. The description of operations on metagraphs and the implementation of algorithms that allow such operations have expanded the possibilities for using the metagraphic data model.

Keywords:Metagraphs, metagraph data model, algorithms, asymptotic complexity estimation, discrete mathematics