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

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

Dates:

Submitted:	Dec 17, 2025
Accepted:	Mar 23, 2026
Published print:	Oct 1, 2026
Published online:	Oct 1, 2026

Identifiers:

≡ Elibrary:

93219250

Altmetrics: