Рекурсивно-параллельный алгоритм решения задачи об изоморфизме граф-подграф

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