Back to search

University of Victoria (Canada)

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Mathematics and Statistics
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Duffy, Christopher
Advisor dc:contributor.supervisor
  • MacGillivray, Gary

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/3550

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Duffy, Christopher. A collection of algorithmic and complexity results for variants of the Firefighter Problem. Master of Science M.Sc. thesis, 2011. http://hdl.handle.net/1828/3550