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

Abstract

Объектом исследования являются задачи дискретной оптимизации и задачи теории графов. Цель работы состоит в разработке методов и алгоритмов дискретной математики для решения задач оптимизации, характеризации и распознавания, формулируемых в терминах теории графов, теории расписаний, разбиений и упаковки. Основные результаты исследований. Разработаны рекордные алгоритмы для семи онлайн версий задач теории расписаний с убывающими длительностями обслуживания и для онлайн версий задач упаковки с растяжением. Разработан асимптотически наилучший алгоритм для задачи теории расписаний Pm||Cmax с известной суммарной длительностью всех работ, основанный на использовании групповых технологий и вычислении динамической нижней оценки. Построены эффективные алгоритмы для решения задачи двумерного прямоугольного гильотинного раскроя полосы и прямоугольника. Для задачи теории расписаний Om||Cmax найдены новые свойства экстремальных плотных расписаний. Установлена вычислительная сложность и сложность аппроксимации и найдены полиномиально разрешимые случаи для ряда теоретико-графовых задач, связанных с понятиями независимости, доминирования и паросочетания в наследственных классах графов. Установлена co-NP-полнота задачи распознавания класса графов, в которых все максимальные индуцированные паросочетания имеют одинаковый размер, и найдена его характеризация в терминах минимальных запрещенных косогласованных подграфов. Получены новые достаточные условия полной циклической расширяемости графов и установлена вычислительная сложность задачи о гамильтоновом цикле в ряде классов графов с предписанными локальными ограничениями.