Recursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problem

Abstract

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
• isomorphism
• parallel algorithm
• recursion
• .net