Exact Solutions for the Moving Firefighter Problem on Trees
Networks · 2026-07 · 88 (1) · 42-58
DOI: 10.1002/net.70037 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 28.03.2026. Verfasst von Mauro A. Montenegro‐Meza und 4 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Secretaría de Ciencia, Humanidades, Tecnología e Innovación, Instituto Politécnico Nacional.
Abstract (Originalsprache)
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.
Förderung
- Secretaría de Ciencia, Humanidades, Tecnología e Innovación
- Instituto Politécnico Nacional
Zitieren
APA
Montenegro‐Meza, M. A., Corona‐Bermúdez, U., Menchaca‐Méndez, R., Menchaca‐Méndez, R., & Cornejo‐Acosta, J. A. (2026). Exact Solutions for the Moving Firefighter Problem on Trees. Networks, 88(1), 42-58. https://doi.org/10.1002/net.70037
Vancouver
Montenegro‐Meza MA, Corona‐Bermúdez U, Menchaca‐Méndez R, Menchaca‐Méndez R, Cornejo‐Acosta JA. Exact Solutions for the Moving Firefighter Problem on Trees. Networks. 2026;88(1):42-58. doi:10.1002/net.70037
BibTeX
@article{MontenegroMeza2026,
author = {Montenegro‐Meza, Mauro A. and Corona‐Bermúdez, Uriel and Menchaca‐Méndez, Rolando and Menchaca‐Méndez, Ricardo and Cornejo‐Acosta, José Alejandro},
title = {Exact Solutions for the Moving Firefighter Problem on Trees},
journal = {Networks},
year = {2026},
volume = {88},
number = {1},
pages = {42--58},
doi = {10.1002/net.70037}
}
EUVIMED