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

Abstract

Объектами исследования являются задачи дискретной оптимизации, теории графов и булевых функций. Целью работы стало создание методов и эффективных алгоритмов для задач, возникающих в сложных дискретных системах, моделируемых в терминах объектов комбинаторной природы (графов, гиперграфов, расписаний, разбиений, булевых функций). В результате разработаны методы, позволяющие строить приближенные алгоритмы и оценивать их качество для задач теории расписаний и упаковки с неполной информацией. Установлены структурные свойства и получены характеризации специальных классов графов, определяемых в терминах свойств окружений вершин. Выделены полиномиально разрешимые и NP-трудные случаи ряда задач комбинаторной оптимизации, связанных с понятиями паросочетания, независимости и доминирования, установлена сложность аппроксимации рассматриваемых задач. В ряде новых классов графов доказана гипотеза Хартсфилда-Рингеля об антимагичности. Решена задача характеризации и/или оценена вычислительная сложность задачи распознавания для некоторых классов графов пересечений ребер гиперграфов ограниченных ранга и кратности при априорных ограничениях. Разработан полиномиальный алгоритм распознавания A4-структуры (2, 1)-простого графа. Получен поисковый алгоритм и алгоритм генерации графов для выполнения социофизического моделирования в рамках социальной сети. Предложены новые подходы к проектированию элементов вычислительной техники на основе использования различных свойств булевых функций и комбинаций их представлений.