The Moving Firefighter Problem

Bruno R. Gutiérrez- De-La-Paz, Jesús García-Díaz, Rolando Menchaca-Méndez (), Mauro A. Montenegro-Meza, Ricardo Menchaca-Méndez and Omar A. Gutiérrez- De-La-Paz
Additional contact information
Bruno R. Gutiérrez- De-La-Paz: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Jesús García-Díaz: Consejo Nacional de Ciencia y Tecnología, Mexico City 03940, Mexico
Rolando Menchaca-Méndez: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Mauro A. Montenegro-Meza: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Ricardo Menchaca-Méndez: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico
Omar A. Gutiérrez- De-La-Paz: Centro de Investigación en Computación del Instituto Politécnico Nacional, Mexico City 07738, Mexico

Mathematics, 2022, vol. 11, issue 1, 1-15

Abstract: The original formulation of the firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G . At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless they are defended by a firefighter that can move between any pair of vertices in a single time unit. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread. In this work, we present the moving firefighter problem, which is a generalization of the firefighter problem where the time it takes a firefighter to move from a vertex u to defend vertex v is determined by a function τ . This new formulation models situations such as a wildfire or a flood, where firefighters have to physically move from their current position to the location of an entity they intend to defend. It also incorporates the notion that entities modeled by the vertices are not necessarily instantaneously defended upon the arrival of a firefighter. We present a mixed-integer quadratically constrained program (MIQCP) for the optimization version of the moving firefighter problem that minimizes the number of burnt vertices for the case of general finite graphs, an arbitrary set F ⊂ V of vertices where the fire breaks out, a single firefighter, and metric time functions τ .

Keywords: firefighter problem; np-hard; mathematical programming; mixed-integer quadratically constrained programming (MIQCP); exact algorithm; spread and containment in networks (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/1/179/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/1/179/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2022:i:1:p:179-:d:1019106

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().