EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Exact Solutions for the Moving Firefighter Problem on Trees

Mauro A. Montenegro‐Meza, Uriel Corona‐Bermúdez, Rolando Menchaca‐Méndez, Ricardo Menchaca‐Méndez, José Alejandro Cornejo‐Acosta

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →