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

Библиографическая ссылка: Жуков Г.А. , Ерзин А.И. , Плотников Р.В.
Метод ветвей и отсечений для задачи взвешенной 3-раскраски графа
Дискретный анализ и исследование операций. 2026. Т.33. №2. С.46-63. DOI: 10.33048/daio.2026.33.848 РИНЦ

Даты:

Поступила в редакцию:	17 дек. 2025 г.
Принята к публикации:	23 мар. 2026 г.
Опубликована в печати:	1 окт. 2026 г.
Опубликована online:	1 окт. 2026 г.

Идентификаторы БД:

≡ РИНЦ:

93219250

Альметрики: