Name
Abstract | ||
|---|---|---|
Hartnell's firefighter game models the containment of the spreading of an undesired property within a network. It is a one-player game played in rounds on a graph G in which a fire breaks out at f vertices of G. In each round the fire spreads to neighboring vertices unless the player defends these. The power of the player is limited in the sense that he can defend at most d additional vertices of G in each round. His objective is to save as many vertices as possible from burning. Most research on this game concerned the case f=d=1, which already leads to hard problems even restricted to trees. We study the game for larger values of f and d. We present useful properties of optimal strategies for the game on trees, efficient approximation algorithms, and bounds on the so-called surviving rate. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2013.04.008 | Discrete Applied Mathematics |
Keywords | Field | DocType |
undesired property,larger value,one-player game,neighboring vertex,hard problem,additional vertex,graph g,efficient approximation algorithm,optimal strategy,firefighter game model | Discrete mathematics,Graph,Approximation algorithm,Combinatorics,Vertex (geometry),Game tree,Mathematics | Journal |
Volume | Issue | ISSN |
161 | 16-17 | 0166-218X |
Citations | PageRank | References |
16 | 0.74 | 6 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vitor Costa | 1 | 27 | 4.27 |
| Simone Dantas | 2 | 119 | 24.99 |
| Mitre C. Dourado | 3 | 242 | 18.13 |
| Lucia Draque Penso | 4 | 196 | 20.46 |
| Dieter Rautenbach | 5 | 946 | 138.87 |