Sciact
  • EN
  • RU

Minimizing the sum of weights of single-color edges in a 3-coloring Научная публикация

Конференция XV International Conference Optimization and Applications (OPTIMA-2024)
16-20 сент. 2024 , Petrovac
Сборник Advances in Optimization and Applications
Сборник, 2025.
Журнал Communications in Computer and Information Science
ISSN: 1865-0929
Вых. Данные Год: 2025,
Ключевые слова 3-coloring, Approximation, Simulation
Авторы Erzin A. 1,2 , Plotnikov R. 1 , Zhukov G. 2
Организации
1 Sobolev Institute of Mathematics, SB RAS, Novosibirsk 630090, Russia
2 Novosibirsk State University, Novosibirsk 630090, Russia

Информация о финансировании (1)

1 Институт математики им. С.Л. Соболева СО РАН FWNF-2022-0019

Реферат: A proper coloring of the graph's vertices with a bounded number of colors is an NP-hard problem, and there are various papers devoted to it. Less studied is the problem of coloring the vertices of a weighted graph in such a way as to minimize the total weight of edges with incident vertices of the same color (single-color edges). In this paper, we consider the coloring of graph vertices with 3 colors, which is NP-hard even for a planar graph. Then, we focus on developing the approximation algorithms. The developed algorithms were tested both on random graphs and on industrial graphs. The intensive numerical experiment con rms the high e ciency of the proposed approach.
Библиографическая ссылка: Erzin A. , Plotnikov R. , Zhukov G.
Minimizing the sum of weights of single-color edges in a 3-coloring
В сборнике Advances in Optimization and Applications. 2025.
Идентификаторы БД: Нет идентификаторов
Цитирование в БД: Пока нет цитирований