O Problema do Brigadista com Vértices Resistentes

  • Luis Filipe de Lima Sales IFCE
  • Raimundo Azevedo Neto IFCE
  • Glauber Ferreira Cintra IFCE

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.
Publicado
30/06/2020
Como Citar

Selecione um Formato
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.