Решение задачи поиска граф-подграф изоморфизма для распределения ресурсов организации

Abstract

RU: В работе представлен граф-аналитический подход к распределению ресурсов организации. Он основан на алгоритме поиска граф-подграф изоморфизма для взвешенных и помеченных графов и является развитием алгоритма поиска граф-подграф изоморфизма для взвешенных графов. UK: У роботі запропоновано граф-аналітичний підхід для розподілу ресурсів організації. Він базується на алгоритмі пошуку граф-підграф ізоморфізму для зважених та помічених графів і є розвитком алгоритму пошуку граф-підграф ізоморфізму для зважених графів. EN: The paper presents graph-analytical approach for organizations resources distribution. It based on graph-subgraph isomorphism algorithm for weighted and labeled graphs and can be considered as development of graph-subgraph isomorphism algorithm for weighted graphs proposed before. Paper describes requirements and specifics of human and technical resources reservation in modern distributed organizations, that can have rather complicated structure, taking into account relations between available resources, and specifics of requirements in resources provided by complicated tasks that need to be solved by organizations. All types of resources considered as weighted and labeled graphs. Next presented advanced version of graph-subgraph isomorphism algorithm enhanced to work with graphs both weighted and labeled by vertexes. Provided full set of preliminary conditions aim to narrow main combinatorial part of algorithm, where branch and bound method used to find final substitution. Finally presented numerical results of algorithm benchmarking on randomly generated sets of graphs represented most severe possible conditions for realistic graphs organization in possible practical applications and grounded developed algorithm productivity being enough for solving real scale resources distribution problems on existed hardware.