Исследование задачи одностороннего доминирования с запретами

Abstract

В работе рассматривается обобщение задачи одностороннего доминирования в двудольном графе. Пусть имеется двудольный граф G с долями V1, V2 и семейство S непустых подмножеств S1, S2, … , St множества вершин доли V2. Задача состоит в том, чтобы найти наименьшее (по числу вершин) подмножество D доли V2 такое, что каждая вершина доли V1 смежна по крайней мере с одной из вершин множества D и множество D содержит не более одной вершины из каждого множества Si семейства S. Особенность задачи заключается в наличии семейства S «запрещающих» множеств. В работе исследуется вычислительный аспект указанной задачи, а именно формулируется её содержательная и распознавательная постановки, устанавливается вычислительная сложность и предлагается целочисленная линейная модель задачи. Кроме этого, разработаны и протестированы на случайных графах следующие эвристические алгоритмы, решающие указанную задачу приближённо: локальный поиск, метод имитации отжига, жадный алгоритм. Проведён сравнительный анализ работы алгоритмов.