2005-23: Fractional Firefighting in the Two Dimensional Grid

DIMACS TR: 2005-23

Fractional Firefighting in the Two Dimensional Grid

Authors: K. L. Ng and P. Raff

ABSTRACT
We consider a generalization of the firefighter problem where the number of firefighters available per time step $t$ is not a constant. We show that if the number of firefighters available is periodic in $t$ and the average number per time step exceeds $\frac{3}{2}$, then a fire starting at a finite number of vertices in the two dimensional infinite grid graph can be contained.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-23.ps.gz

DIMACS Home Page