Firefighting with general weights
Vitor Costa, Simone Dantas, Mitre Costa Dourado, Lúcia Draque Penso, Dieter Rautenbach · Scuola Normale Superiore eBooks · 2013
At the 25th Manitoba Conference on Combinatorial Mathematics and Computing in Winnipeg 1995 Hartnell introduced the firefighter game modelling the containment of the spreading of an undesired property within a network. An initial configuration of the game consists of a pair ( G, r ) where G is a finite, simple, and undirected graph and r is a burned vertex of G . The game proceeds in rounds. In each round, first at most one vertex of G that is not burned is defended and then all vertices of G that are neither burned nor defended and have a burned neighbor are burned. Once a vertex is burned or defended, it remains so for the rest of the game. The game ends with the first round, in which no further vertex is burned. All vertices of G that are not burned at the end of the game are saved. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.