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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2023},
     volume = {19},
     number = {1},
     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
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
%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/

[1] Olemskoy I. V., Hitrov G. M., Vitashevskaya I. S. On some invariants of square (0,1)-matrices, Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2007, no. 1, 38–45 (In Russian) | Zbl

[2] Firyulina O. S., “Calculation of the nondensity of square (0,1)-matrices”, Proceedings of the XLIII International Scientific Conference of postgraduates and students “Control processes and stability”, St. Petersburg University Press, St. Petersburg, 2012, 55–60 (In Russian)

[3] Kurosh A. G., Higher algebra course, A textbook for universities, Lan' Publ, St. Petersburg, 2021, 432 pp. (In Russian) | MR

[4] Olemskoy I. V., “Algorithm for the identification of structural features”, Nikolay Efimovich Kirin, Collection of articles, ASSPIN Publ, St. Petersburg, 2003, 234–251 (In Russian)

[5] Olemskoy I. V., Methods of integration of systems of structurally separated differential equations, St. Petersburg University Press, St. Petersburg, 2009, 180 pp. (In Russian)

[6] Olemskoy I. V., Firyulina O. S., “Algorithm for finding the maximum independent set”, Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2014, no. 1, 79–89 (In Russian) | MR

[7] Novikov F. A., Discrete mathematics for programmers, A textbook for universities, Piter Publ, St. Petersburg, 2009, 384 pp. (In Russian) | MR

[8] Firyulina O. S., “Finding all maximal independent sets of an undirected graph”, Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Sciences. Control Processes, 2013, no. 1, 63–69 (In Russian)