Abstract:

The paper addresses the problem of finding a vertex 3-coloring of an edge-weighted graph that minimizes the sum of weights of edges connecting vertices of the same color. The problem is formulated as a continuous DC optimization problem, which allows applying the relevant mathematical framework. To solve the continuous problem, specialized local and global search algorithms have been implemented. In the computational experiment, a comparative analysis was conducted between the developed approach and reference methods: a greedy algorithm, the Variable Neighborhood Descent (VND) method, and its multistart version. The obtained results confirm the applicability of DC optimization techniques for solving the weighted 3-coloring problem and reveal promising areas for further research.