Towards a new approach for coloring the vertices of a graph using Monte Carlo Tree Search
Abstract
This paper introduces a new approach to vertex coloring in graphs. This approach consists of randomly adding edges to the graph, aiming to find a supergraph whose chromatic number is close to that of the original graph and requires low computational time to be computed. To guide the random process, we employ Monte Carlo Tree Search. We have found preliminary evidence in favor of the proposed approach.References
Bellare, M., Goldreich, O., e Sudan, M. (1998). Free bits, PCPs, and nonapproximability—towards tight results. SIAM Journal on Computing, 27(3):804–915.
Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256.
Campbell, P. J. (1977). Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia Mathematica, 4(4):397–404.
Coulom, R. (2007). Efficient selectivity and backup operators in Monte-Carlo tree search. Em van den Herik, H. J., Ciancarini, P., e Donkers, H. H. L. M., editores, Computers and Games 2006, volume 4630 de Lecture Notes in Computer Science, páginas 72–83. Springer-Verlag, Berlin.
Karp, R. M. (1972). Reducibility among combinatorial problems. Em Miller, R. E. e Thatcher, J. W., editores, Complexity of Computer Computations, páginas 85–103. Plenum Press, New York. DOI: 10.1007/978-3-540-68279-0_8. Último acesso: 07/03/2024.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., e Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529:484–489.
Trick, M. (1994). Network Resources for Coloring a Graph. [link]. Último acesso: 22/02/2024.
Vasquez, M. e Vimont, Y. (2018). On solving the queen graph coloring problem. Em Brankovic, L., Ryan, J., e Smyth, W., editores, Combinatorial Algorithms 2017, volume 10765 de Lecture Notes in Computer Science, páginas 244–251. Springer, Cham.
Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4):251–256.
Campbell, P. J. (1977). Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia Mathematica, 4(4):397–404.
Coulom, R. (2007). Efficient selectivity and backup operators in Monte-Carlo tree search. Em van den Herik, H. J., Ciancarini, P., e Donkers, H. H. L. M., editores, Computers and Games 2006, volume 4630 de Lecture Notes in Computer Science, páginas 72–83. Springer-Verlag, Berlin.
Karp, R. M. (1972). Reducibility among combinatorial problems. Em Miller, R. E. e Thatcher, J. W., editores, Complexity of Computer Computations, páginas 85–103. Plenum Press, New York. DOI: 10.1007/978-3-540-68279-0_8. Último acesso: 07/03/2024.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., e Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529:484–489.
Trick, M. (1994). Network Resources for Coloring a Graph. [link]. Último acesso: 22/02/2024.
Vasquez, M. e Vimont, Y. (2018). On solving the queen graph coloring problem. Em Brankovic, L., Ryan, J., e Smyth, W., editores, Combinatorial Algorithms 2017, volume 10765 de Lecture Notes in Computer Science, páginas 244–251. Springer, Cham.
Published
2024-07-21
How to Cite
SOUZA, Raquel M. de; OLIVEIRA, Fabiano de S.; PINTO, Paulo Eustáquio D.; BARBOSA, Valmir C..
Towards a new approach for coloring the vertices of a graph using Monte Carlo Tree Search. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 9. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 38-42.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2024.2336.
