O Problema do Brigadista com Vértices Resistentes
Resumo
Este artigo apresenta uma nova variante do Problema do Brigadista, chamada de Problema do Brigadista com Vértices Resistentes, que se distingue pela presença de uma resistencia ao fogo inteira associada a cada vértice. Apresentamos cinco heurísticas para o problema e os resultados obtidos em testes computacionais.
Palavras-chave:
Grafos, Problema do Brigadista, Otimização Combinatória, Metaheurísticas
Referências
Develin, M. and Hartke, S. G. (2007). Fire containment in grids of dimension three and higher. In Discrete Applied Mathematics, volume 155, pages 2257–2268. Elsevier.
García-Martínez, C., Blum, C., Rodriguez, F., and Lozano, M. (2015). The firefighter problem: Empirical results on random graphs. In Computers and Operational Research, pages 55–66. Elsevier.
Hartnell, B. (1995). Firefighter! an application of domination. Winnipeg, Canada. 25th Manitoba Conference on Combinatorial Mathematics and Computing.
Ramos, N. (2018). Um estudo computacional do problema do brigadista em grafos. Universidade Estadual de Campinas.
García-Martínez, C., Blum, C., Rodriguez, F., and Lozano, M. (2015). The firefighter problem: Empirical results on random graphs. In Computers and Operational Research, pages 55–66. Elsevier.
Hartnell, B. (1995). Firefighter! an application of domination. Winnipeg, Canada. 25th Manitoba Conference on Combinatorial Mathematics and Computing.
Ramos, N. (2018). Um estudo computacional do problema do brigadista em grafos. Universidade Estadual de Campinas.
Publicado
30/06/2020
Como Citar
SALES, Luis Filipe de Lima; AZEVEDO NETO, Raimundo; CINTRA, Glauber Ferreira.
O Problema do Brigadista com Vértices Resistentes. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 61-64.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2020.11090.
