The ACO Seminar (2010-2011)
, 3:30pm, Wean 8220
, Tel Aviv University
3/2 Firefighters are not enough
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.
Joint work with Ohad Feldheim.
Back to the ACO home page