Geodesic
Parallel algorithm for solving the graph isomorphism problem
Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 1, pp. 86-94

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

In this paper, we offer an efficient parallel algorithm for solving the Graph Isomorphism Problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges, it is assumed that the graphs can be disconnected. The question of the existence or absence of an algorithm for solving this problem with polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises of accelerating its solution by parallelizing the algorithm. We used the RPM_ParLib library developed by the author as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. Specially generated random regular graphs with varying degrees of vertices were used as initial data. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.
Keywords: graph isomorphism problem, parallel algorithm, recursion
Mots-clés : .NET. 
@article{MAIS_2020_27_1_a6,
     author = {V. V. Vasilchikov},
     title = {Parallel algorithm for solving the graph isomorphism problem},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {86--94},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a6/}
}
TY  - JOUR
AU  - V. V. Vasilchikov
TI  - Parallel algorithm for solving the graph isomorphism problem
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2020
SP  - 86
EP  - 94
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a6/
LA  - ru
ID  - MAIS_2020_27_1_a6
ER  - 
%0 Journal Article
%A V. V. Vasilchikov
%T Parallel algorithm for solving the graph isomorphism problem
%J Modelirovanie i analiz informacionnyh sistem
%D 2020
%P 86-94
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a6/
%G ru
%F MAIS_2020_27_1_a6
V. V. Vasilchikov. Parallel algorithm for solving the graph isomorphism problem. Modelirovanie i analiz informacionnyh sistem, Tome 27 (2020) no. 1, pp. 86-94. http://geodesic.mathdoc.fr/item/MAIS_2020_27_1_a6/