Комбинаторные модели и методы для решения задач теории расписаний и задач на графах и геометрических структурах : отчет о научно-исследовательской работе (заключительный) / БГУ; научный руководитель В.М. Котов

Abstract

Объектом исследования являются расписания и комбинаторно-геометриче-ские конфигурации (графы, гиперграфы, частично-выпуклые множества). Цель работы состоит в исследовании комбинаторных моделей и разработке методов решения ряда характеризационных, распознавательных и оптимизационных задач, связанных с расписаниями, графами и специальными объектами комбинаторно-геометрической природы. Основные результаты исследований. Предложен алгоритм, имеющий асимптотическую оценку 2, для классической задачи минимизации времени завершения проекта на многопроцессорной системе. Получена характеризация класса графов с ограниченной обобщенной краусовой размерностью при заданных дополнительных ограничениях. Разработаны эффективные полиномиальные алгоритмы решения проблемы распознавания частичной выпуклости объединения нескольких многогранных множеств. Найдены новые достаточные условия гамильтоновости графов и установлена сложность задачи распознавания гамильтоновости для ряда классов графов с предписанными локальными ограничениями. Разработаны алгоритмы для решения задачи о взвешенной независимой {K1, K2}-упаковке в классе деревьев с трудоемкостью O(n) и в классе унициклических графов с трудоемкостью O(n2), где n – число вершин в графе. Для задачи о бикликовом покрытии вершин графа построены полиномиальные приближенные алгоритмы с гарантированными оценками точности в виде частичных сумм гармонического ряда и доказана ее неаппроксимируемость за полиномиальное время с логарифмической гарантированной оценкой точности, в предположении, что P ≠ NP, даже в случае, когда входной граф является сбалансированным двудольным.