Geodesic
Recursive-parallel algorithm for solving the maximum common subgraph problem
Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 2, pp. 128-139

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper proposes an algorithm for solving the problem of finding the maximum common subgraph. Both the sequential and the parallel version of the algorithm, their software implementation are described, and an experimental study of their effectiveness is carried out. This problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems related to the study of complex structures. We solve it in a statement when we need to find all possible isomorphisms of the found common subgraph. Due to the extremely high complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm. To organize parallel computing, the author used the RPM_ParLib library. It allows to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework.The library supports a recursive-parallel programming style and provides effective work distribution and dynamic load balancing of computational modules during program execution. It can be used for applications written in any programming language supported by the .NET Framework. The purpose of the numerical experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. For the experiment, the author developed a special application in the C# language designed to generate various sets of initial data with specified parameters. The paper describes the features of the generated initial pairs of graphs, as well as the results obtained during the experiment.
Keywords: maximum common subgraph, parallel algorithm, recursion
Mots-clés : isomorphism, .NET. 
@article{MAIS_2023_30_2_a1,
     author = {V. V. Vasilchikov},
     title = {Recursive-parallel algorithm for solving the maximum common subgraph problem},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {128--139},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a1/}
}
TY  - JOUR
AU  - V. V. Vasilchikov
TI  - Recursive-parallel algorithm for solving the maximum common subgraph problem
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2023
SP  - 128
EP  - 139
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a1/
LA  - ru
ID  - MAIS_2023_30_2_a1
ER  - 
%0 Journal Article
%A V. V. Vasilchikov
%T Recursive-parallel algorithm for solving the maximum common subgraph problem
%J Modelirovanie i analiz informacionnyh sistem
%D 2023
%P 128-139
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a1/
%G ru
%F MAIS_2023_30_2_a1
V. V. Vasilchikov. Recursive-parallel algorithm for solving the maximum common subgraph problem. Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 2, pp. 128-139. http://geodesic.mathdoc.fr/item/MAIS_2023_30_2_a1/