Geodesic
Algorithm for optimal coloring of square $(0,1)$-matrices
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 19 (2023) no. 1, pp. 90-108

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : $(0,1)$-matrix. 
@article{VSPUI_2023_19_1_a7,
     author = {I. V. Olemskoy and O. S. Firyulina},
     title = {Algorithm for optimal coloring of square $(0,1)$-matrices},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {90--108},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2023_19_1_a7/}
}
TY  - JOUR
AU  - I. V. Olemskoy
AU  - O. S. Firyulina
TI  - Algorithm for optimal coloring of square $(0,1)$-matrices
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2023
SP  - 90
EP  - 108
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2023_19_1_a7/
LA  - ru
ID  - VSPUI_2023_19_1_a7
ER  - 
%0 Journal Article
%A I. V. Olemskoy
%A O. S. Firyulina
%T Algorithm for optimal coloring of square $(0,1)$-matrices
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2023
%P 90-108
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VSPUI_2023_19_1_a7/
%G ru
%F VSPUI_2023_19_1_a7
I. V. Olemskoy; O. S. Firyulina. Algorithm for optimal coloring of square $(0,1)$-matrices. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 19 (2023) no. 1, pp. 90-108. http://geodesic.mathdoc.fr/item/VSPUI_2023_19_1_a7/