Computer science

Algorithm for optimal coloring of square $(0,1)$-matrices

I. V. Olemskoy, O. S. Firyulina

St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation

Abstract: The paper proposes an algorithm for solving the configuration-optimization coloring problem for square $(0,1)$-matrices, which is based on the method of selection their structural features. The algorithm belongs to the method's of backtracking, however, the construction of the optimal solution is carried out among the options that provide a certain configuration, due to which the size of the search tree is significantly reduced. A detailed scheme of its operation is given, and the effectiveness of the solution is demonstrated by the example of calculating the chromatic number of a specific $(0,1)$-matrix.

Keywords: graph coloring, chromatic number, $(0,1)$-matrix.

UDC: 519.174, 519.854.64

MSC: 05C15, 05C85

Received: December 1, 2022
Accepted: January 19, 2023

DOI: 10.21638/11701/spbu10.2023.108