Abstract: The firefighter problem is a monotone dynamic process in graphs that can be viewed as modeling the use of a limited supply of vaccinations to stop the spread of an epidemic. In more detail, a fire spreads through a graph, from burning vertices to their unprotected neighbors. In every round, a small amount of unburnt vertices can be protected by firefighters. How many firefighters per turn, on average, are needed to stop the fire from advancing? We prove tight lower and upper bounds on the amount of firefighters needed to control a fire in the Cartesian planar grid and in the strong planar grid, resolving two conjectures of Ng and Raff.
Recommendations
Cited in
(13)- Finding exact solutions for the geometric firefighter problem in practice
- Surviving rate of graphs and firefighter problem
- Firefighting on trees
- Fire containment in grids of dimension three and higher
- A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
- Multi-layered planar firefighting
- Towards more efficient infection and fire fighting
- The firefighter problem: empirical results on random graphs
- Average firefighting on infinite grids
- scientific article; zbMATH DE number 1506515 (Why is no real title available?)
- Firefighting on square, hexagonal, and triangular grids
- The coarse geometry of Hartnell's firefighter problem on infinite graphs
- Firefighting as a strategic game
This page was built for publication: 3/2 firefighters are not enough
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759889)
