Exact solutions for the moving firefighter problem on trees

DOI10.1002/NET.70037MaRDI QIDQ7267803zbMATH OpenFDO

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

Publication date 16 June 2026

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/NET.70037

zbMATH Keywords

dynamic programmingfirefighter probleminteger programmingNP-hardnessquadratic programmingspread and containment in networks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Integer programming (90C10) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Cites work

• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Approximability of the firefighter problem. Computing cuts over time
• Approximation algorithms for the firefighter problem: cuts over time and submodularity
• Approximation algorithms for the geometric firefighter and budget fence problems
• Approximation algorithms for the geometric firefighter and budget fence problems
• Fast random generation of binary, t-ary and other types of trees
• Fighting constrained fires in graphs
• Fire containment in grids of dimension three and higher
• Firefighting on trees
• Firefighting on trees beyond integrality gaps
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Firefighting on trees: How bad is the greedy algorithm?
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• New integrality gap results for the firefighters problem on trees
• Online firefighting on trees
• Parameterized complexity of firefighting
• Solving the geometric firefighter routing problem via integer programming
• The firefighter problem for cubic graphs
• The firefighter problem for graphs of maximum degree three
• The firefighter problem on graph classes
• The firefighter problem with more than one firefighter on trees
• The Firefighter problem: a survey of results, directions and questions
• The firefighter problem: further steps in understanding its complexity

This page was built for publication: Exact solutions for the moving firefighter problem on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7267803)