Minimizing the sum of weights of single-color edges in a 3-coloring Full article
| Conference |
XV International Conference Optimization and Applications (OPTIMA-2024) 16-20 Sep 2024 , Petrovac |
||||
|---|---|---|---|---|---|
| Source | Advances in Optimization and Applications Compilation, 2025. |
||||
| Journal |
Communications in Computer and Information Science
ISSN: 1865-0929 |
||||
| Output data | Year: 2025, | ||||
| Tags | 3-coloring, Approximation, Simulation | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0019 |
Abstract:
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.
Cite:
Erzin A.
, Plotnikov R.
, Zhukov G.
Minimizing the sum of weights of single-color edges in a 3-coloring
In compilation Advances in Optimization and Applications. 2025.
Minimizing the sum of weights of single-color edges in a 3-coloring
In compilation Advances in Optimization and Applications. 2025.
Identifiers:
No identifiers
Citing:
Пока нет цитирований