Exact Solutions for the Moving Firefighter Problem on Trees

Read full text Summarise with VIRAT
Authors: Mauro Alejandro Montenegro Meza, Uriel Corona-Bermúdez, Rolando Menchaca-Méndez, Ricardo Menchaca‐Méndez, José Alejandro Cornejo-Acosta
Cited by: 0
References: 26

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

ABSTRACT The moving firefighter problem (MFP) is a more realistic variant of the classic firefighter problem (FP), where firefighters require time for both travel and defense. Unfortunately, the only known exact solution for the MFP does not scale. In this paper, we establish that the MFP is NP‐complete on trees of maximum degree three and present four alternative methods to find exact solutions for the case of arbitrary trees with a single initial fire and one firefighter. The first method is a dynamic programming algorithm, while the other three methods are based on mathematical programming: an integer quadratically constrained program (IQCP), and two distinct integer linear programs (ILP and E‐ILP). Our mathematical programming formulations exploit the inherent properties of tree topologies to significantly improve scalability by reducing the number of decision variables and constraints relative to those for arbitrary graphs. We present a comprehensive experimental analysis of the performance and scalability of the proposed solutions.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Facility Location and Emergency Management

Publication details

Journal / source
Networks
Volume
88
Issue
1
Pages
42–58
Publication date
28 March 2026
Language
EN