The Firefighter Process models the spread and defence of a fire using a simple graph. We consider the following discrete-time process: at t = 0 some vertex of the graph begins burning. At each subsequent step we may defend a vertex from burning and the fire spreads from all burning vertices to all undefended neighbours. We consider the related problems of maximising the number of saved vertices, protecting a specified set from burning and maximising the weight of the saved vertices. We close three open problems concerning these decision problems and their related optimisation problems using the notion of a strategy, the sequence of defended vertices. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3550 |
| Date | 02 September 2011 |
| Creators | Duffy, Christopher |
| Contributors | MacGillivray, Gary |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0023 seconds