The Firefighter Problem with Resistant Vertices

  • Luis Filipe de Lima Sales IFCE
  • Raimundo Azevedo Neto IFCE
  • Glauber Ferreira Cintra IFCE
DOI: https://doi.org/10.5753/etc.2020.11090

Abstract


This paper presents a new variant of the Firefighter Problem, namely, the Firefighter Problem with Resistant Vertices, that distinguishes itself through the existence of an integer fire resistance associated with each vertex. We present five heuristics to the problem and the results obtained in computational tests.

Keywords: Graphs, Firefighter Problem, Combinatorial Optimization, Metaheuristics

References

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.
Published
2020-06-30
How to Cite

Select a Format
SALES, Luis Filipe de Lima; AZEVEDO NETO, Raimundo; CINTRA, Glauber Ferreira. The Firefighter Problem with Resistant Vertices. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.