Name
Abstract | ||
|---|---|---|
The firefighter problem is a simplified model for the spread of a fire (or disease or computer virus) in a network. A fire breaks out at a vertex in a connected graph, and spreads to each of its unprotected neighbours over discrete time-steps. A firefighter protects one vertex in each round which is not yet burned. While maximizing the number of saved vertices usually requires a strategy on the part of the firefighter, the fire itself spreads without any strategy. We consider a variant of the problem where the fire is constrained by spreading to a fixed number of vertices in each round. In the two-player game of k-firefighter, for a fixed positive integer k, the fire chooses to burn at most k unprotected neighbours in a given round. The k-surviving rate of a graph G is defined as the expected percentage of vertices that can be saved in k-firefighter when a fire breaks out at a random vertex of G. We supply bounds on the k-surviving rate, and determine its value for families of graphs including wheels and prisms. We show using spectral techniques that random d regular graphs have k-surviving rate at most (1+O(d^-^1^/^2))k+1. We consider the limiting surviving rate for countably infinite graphs. In particular, we show that the limiting surviving rate of the infinite random graph can be any real number in [1/(k+1),1]. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.01.041 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
real number,firefighter problem,k-surviving rate,regular graph,random vertex,connected graph,graph G,fixed number,countably infinite graph,infinite random graph | Journal | 434, |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anthony Bonato | 1 | 156 | 18.57 |
| Margaret-Ellen Messinger | 2 | 63 | 9.83 |
| Pawe Praat | 3 | 27 | 2.84 |