Minimizing the sum of weights of single-color edges in a 3-coloring | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

Communications in Computer and Information Science
ISSN: 1865-0929

Вых. Данные

Год: 2025,

Ключевые слова

3-coloring, Approximation, Simulation

Авторы

Erzin A. ^1,2 , Plotnikov R. ¹ , Zhukov G. ²

Организации

1	Sobolev Institute of Mathematics, SB RAS, Novosibirsk 630090, Russia
2	Novosibirsk State University, Novosibirsk 630090, Russia

Информация о финансировании (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
Communications in Computer and Information Science. 2025.

Нет идентификаторов

Пока нет цитирований