کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420901 | 683998 | 2007 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Fire containment in grids of dimension three and higher Fire containment in grids of dimension three and higher](/preview/png/420901.png)
We consider a deterministic discrete-time model of fire spread introduced by Hartnell [Firefighter! an application of domination, Presentation, in: 20th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada, September 1995] and the problem of minimizing the number of burnt vertices when a fixed number of vertices can be defended by firefighters per time step. While only two firefighters per time step are needed in the two-dimensional lattice to contain any outbreak, we prove a conjecture of Wang and Moeller [Fire control on graphs, J. Combin. Math. Combin. Comput. 41 (2002) 19–34] that 2d-12d-1 firefighters per time step are needed to contain a fire outbreak starting at a single vertex in the d -dimensional square lattice for d⩾3d⩾3; we also prove that in the d -dimensional lattice, d⩾3d⩾3, for each positive integer f there is some outbreak of fire such that f firefighters per time step are insufficient to contain the outbreak. We prove another conjecture of Wang and Moeller that the proportion of elements in the three-dimensional grid Pn×Pn×PnPn×Pn×Pn which can be saved with one firefighter per time step when an outbreak starts at one vertex goes to 0 as n gets large. Finally, we use integer programming to prove results about the minimum number of time steps needed and minimum number of burnt vertices when containing a fire outbreak in the two-dimensional square lattice with two firefighters per time step.
Journal: Discrete Applied Mathematics - Volume 155, Issue 17, 15 October 2007, Pages 2257–2268