Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem
The paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems associated with the study of com...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2022-03-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1606 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849338895779495936 |
|---|---|
| author | Vladimir V. Vasilchikov |
| author_facet | Vladimir V. Vasilchikov |
| author_sort | Vladimir V. Vasilchikov |
| collection | DOAJ |
| description | The paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems associated with the study of complex structures. We solve the problem in a formulation that requires finding all existing isomorphic substitutions or proving their absence. In view of the high complexity of the problem, it is natural to want to speed up 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 under the control of the runtime environment .NET Framework. Thanks to this library, 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 of the .NET Framework can be used as a programming language in conjunction with this library. For the numerical experiment, an open database from the Internet was used, which was specially developed to study algorithms for searching for isomorphic substitutions. Also, the author has developed a special application in C# for generating additional sets of initial data with specified characteristics. The aim of the experiment was to study the speedup achieved due to the recursively parallel organization of computations. The paper provides a detailed description of the proposed algorithm, as well as the results obtained during the experiment. |
| format | Article |
| id | doaj-art-182709fc632740b69f21ec54ae71d3d5 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2022-03-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-182709fc632740b69f21ec54ae71d3d52025-08-20T03:44:17ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172022-03-01291304310.18255/1818-1015-2022-1-30-431233Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism ProblemVladimir V. Vasilchikov0P. G. Demidov Yaroslavl State UniversityThe paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems associated with the study of complex structures. We solve the problem in a formulation that requires finding all existing isomorphic substitutions or proving their absence. In view of the high complexity of the problem, it is natural to want to speed up 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 under the control of the runtime environment .NET Framework. Thanks to this library, 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 of the .NET Framework can be used as a programming language in conjunction with this library. For the numerical experiment, an open database from the Internet was used, which was specially developed to study algorithms for searching for isomorphic substitutions. Also, the author has developed a special application in C# for generating additional sets of initial data with specified characteristics. The aim of the experiment was to study the speedup achieved due to the recursively parallel organization of computations. The paper provides a detailed description of the proposed algorithm, as well as the results obtained during the experiment.https://www.mais-journal.ru/jour/article/view/1606graph-subgraph isomorphism problemparallel algorithmrecursion.net |
| spellingShingle | Vladimir V. Vasilchikov Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem Моделирование и анализ информационных систем graph-subgraph isomorphism problem parallel algorithm recursion .net |
| title | Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem |
| title_full | Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem |
| title_fullStr | Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem |
| title_full_unstemmed | Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem |
| title_short | Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem |
| title_sort | recursive parallel algorithm for solving the graph subgraph isomorphism problem |
| topic | graph-subgraph isomorphism problem parallel algorithm recursion .net |
| url | https://www.mais-journal.ru/jour/article/view/1606 |
| work_keys_str_mv | AT vladimirvvasilchikov recursiveparallelalgorithmforsolvingthegraphsubgraphisomorphismproblem |