Return to search

A collection of algorithmic and complexity results for variants of the Firefighter Problem

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

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3550
Date02 September 2011
CreatorsDuffy, Christopher
ContributorsMacGillivray, Gary
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0019 seconds