Em direção a uma nova abordagem para colorir os vértices de um grafo usando Busca Monte Carlo em Árvore
Resumo
Este artigo apresenta uma nova abordagem para coloração de vértices em grafos. Essa abordagem consiste em adicionar arestas ao grafo aleatoriamente, na expectativa de encontrar um supergrafo cujo número cromático seja próximo ao do grafo original e requeira tempo computacional baixo para ser computado. O processo aleatório é guiado pela Busca Monte Carlo em Árvore. Apresentamos evidências preliminares em favor dessa abordagem.Referências
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.
Publicado
21/07/2024
Como Citar
SOUZA, Raquel M. de; OLIVEIRA, Fabiano de S.; PINTO, Paulo Eustáquio D.; BARBOSA, Valmir C..
Em direção a uma nova abordagem para colorir os vértices de um grafo usando Busca Monte Carlo em Árvore. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (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.
