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

Abstract

Объектом исследования являются графо-комбинаторные конфигурации специального вида (разбиения множеств, графы, гиперграфы). Цель работы – разработка методов и алгоритмов решения задач упаков- ки с неполной информацией, методов характеризации и распознавания класса графов пересечений ребер линейных k-хроматических гиперграфов в классах (α,β)-полярных графов, установление вычислительной сложности и сложности аппроксимации ряда модельных задач, связанных с понятиями независимости, доминирования и паросочетания в графах.