Abstract: Работа посвящена решению NP-трудной задачи раскраски вершин рёберно-взвешенного неориентированного графа в 3 цвета с целью минимизации суммарного веса рёбер, соединяющих вершины одного цвета. Данная задача математически эквивалентна известной задаче о максимальном разрезе на k частей (Maximum k-Cut), где требуется максимизировать вес рёбер между вершинами из различных подмножеств. В настоящей работе представлен точный алгоритм для случая k = 3, реализованный в рамках схемы ветвей и отсечений (Branch-and-Cut). В то время как большинство существующих исследований сфокусированы на классах допустимых неравенств, ключевым вкладом данной работы является метод уменьшения глубины дерева ветвления на основе декомпозиции вершин, интегрированный в схему Branch-and-Cut. Вычислительные эксперименты демонстрируют высокую эффективность разработанного алгоритма.

Cite: Жуков Г.А. , Ерзин А.И. , Плотников Р.В.
Метод ветвей и отсечений для задачи взвешенной 3-раскраски графа
Дискретный анализ и исследование операций. 2026. Т.33. №2.

Identifiers: No identifiers