Эффективные алгоритмы решения квадратичной задачи о назначениях для некоторых типов графов

Работа представляет собой изучение квадратичной задачи о назначениях (КЗН) в терминах теории графов и фокусируется на трех полиномиально-разрешимых подзадачах общей КЗН. В общем случае КЗН является NP-трудной задачей. Одной из основных особенностей работы является тот факт, что проблема рассматривается в терминах теории графов, когда неориентированный взвешенный по ребрам граф представляет собой структуру связей между объектами. Рассматривались три эффективно разрешимые подзадачи общей КЗН, а именно: размещение невзвешенной цепи на взвешенном дереве произвольной структуры, размещение взвешенного графа произвольной структуры на взвешенной звезде, размещение взвешенной звезды на взвешенной сети произвольной структуры. Результатом работы является первичная реализация полиномиальных алгоритмов для рассмотренных подзадач. Языком программирования является Python. В частности, были проведены вычислительные эксперименты, подтвердившие на тестовых данных правильность работы алгоритмов и соответствие времени работы заявленным верхним оценками сложности.