maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-2-128-139NPFBHCmais-1775Research ArticleAlgorithmsРекурсивно-параллельный алгоритм поиска максимального общего подграфаRecursive-Parallel Algorithm for Solving the Maximum Common Subgraph Problemhttps://orcid.org/0000-0001-7882-8906ВасильчиковВладимир ВасильевичVasilchikovVladimir V.vvv193@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202314062023302128139Copyright © Васильчиков В.В., 20232023Васильчиков В.В.Vasilchikov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1775

В работе предложен алгоритм решения задачи нахождении максимального общего подграфа. Описаны последовательный и параллельный вариант алгоритма, их программная реализация и произведено экспериментальное исследование их эффективности. Данная задача является одной из самых известных NP"=полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы найденного общего подграфа. Ввиду чрезвычайно высокой трудоемкости задачи желание ускорить ее решение за счет распараллеливания алгоритма является вполне естественным. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Целью численного эксперимента было исследование ускорения, достигаемого за счет рекурсивно"=параллельной организации вычислений. Для эксперимента автором было разработано специальное приложение на языке C#, предназначенное для генерации различных наборов исходных данных с заданными параметрами. В работе описаны характеристики сгенерированных исходных пар графов, а также результаты, полученные в ходе эксперимента.

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.

максимальный общий подграфизоморфизмпараллельный алгоритмрекурсия.NETmaximum common subgraphisomorphismparallel algorithmrecursion.NETЯрГУ ( проект VIP-016)ReferencesM. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Siam Review, vol. 24, no. 1, pp. 90–91, 1982.M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Siam Review, vol. 24, no. 1, pp. 90–91, 1982.R. Hoffmann, C. McCreesh, and C. Reilly, “Between Subgraph Isomorphism and Maximum Common Subgraph,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2017, vol. 31, no. 1, pp. 3907–3914.R. Hoffmann, C. McCreesh, and C. Reilly, “Between Subgraph Isomorphism and Maximum Common Subgraph,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2017, vol. 31, no. 1, pp. 3907–3914.S. N. Ndiaye and C. Solnon, “CP Models for Maximum Common Subgraph Problems,” Lecture Notes in Computer Science, vol. 6876, pp. 637–644, 2011.S. N. Ndiaye and C. Solnon, “CP Models for Maximum Common Subgraph Problems,” Lecture Notes in Computer Science, vol. 6876, pp. 637–644, 2011.D. Conte, P. Foggia, and M. Vento, “Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs,” Journal of Graph Algorithms and Applications, vol. 11, no. 1, pp. 99–143, 2007.D. Conte, P. Foggia, and M. Vento, “Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs,” Journal of Graph Algorithms and Applications, vol. 11, no. 1, pp. 99–143, 2007.J. J. McGregor, “Backtrack search algorithms and the maximal common sub-graph problem,” Software: Practice and Experience, vol. 12, no. 1, pp. 23–34, 1982.J. J. McGregor, “Backtrack search algorithms and the maximal common sub-graph problem,” Software: Practice and Experience, vol. 12, no. 1, pp. 23–34, 1982.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An Improved Algorithm for Matching Large Graphs,” in Proc. of the 3rd IAPR-TC-15 InternationalWorkshop on Graph-based Representations, 2001, pp. 149–159.L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “An Improved Algorithm for Matching Large Graphs,” in Proc. of the 3rd IAPR-TC-15 InternationalWorkshop on Graph-based Representations, 2001, pp. 149–159.P. J. Durand, R. Pasari, J. W. Baker, and C.-che Tsai, “An efficient algorithm for similarity analysis of molecules,” Internet Journal of Chemistry, vol. 2, no. 17, pp. 1–16, 1999.P. J. Durand, R. Pasari, J. W. Baker, and C.-che Tsai, “An efficient algorithm for similarity analysis of molecules,” Internet Journal of Chemistry, vol. 2, no. 17, pp. 1–16, 1999.C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Communications of the ACM, vol. 16, no. 9, pp. 575–577, 1973.C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Communications of the ACM, vol. 16, no. 9, pp. 575–577, 1973.A. Marcelli, S. Quer, and G. Squillero, “The Maximum Common Subgraph Problem: A Portfolio Approach.” 2019, [Online]. Available: http://arxiv.org/abs/1908.06418.A. Marcelli, S. Quer, and G. Squillero, “The Maximum Common Subgraph Problem: A Portfolio Approach.” 2019, [Online]. Available: http://arxiv.org/abs/1908.06418.V. V. Vasilchikov, “Parallel algorithm for solving the graph isomorphism problem,” Modeling and analysis of information systems, vol. 27, no. 1, pp. 86–94, 2020.V. V. Vasilchikov, “Parallel algorithm for solving the graph isomorphism problem,” Modeling and analysis of information systems, vol. 27, no. 1, pp. 86–94, 2020.V. V. Vasilchikov, “Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem,” Modeling and analysis of information systems, vol. 29, no. 1, pp. 30–43, 2022.V. V. Vasilchikov, “Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem,” Modeling and analysis of information systems, vol. 29, no. 1, pp. 30–43, 2022.V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.V. V. Vasilchikov, Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki. YarGU, Yaroslavl, 2001.V. V. Vasilchikov, “On the recursive-parallel programming for the .NET framework,” Automatic Control and Computer Sciences, vol. 48, pp. 575–580, 2014.V. V. Vasilchikov, “On the recursive-parallel programming for the .NET framework,” Automatic Control and Computer Sciences, vol. 48, pp. 575–580, 2014.

The authors declare that there are no conflicts of interest present.