A new survey on the firefighter problem

Show simple item record

dc.contributor.author Wagner, Connor
dc.date.accessioned 2021-09-01T19:35:46Z
dc.date.available 2021-09-01T19:35:46Z
dc.date.copyright 2021 en_US
dc.date.issued 2021-09-01
dc.identifier.uri http://hdl.handle.net/1828/13360
dc.description.abstract Firefighter is a discrete-time dynamic process that models the spread of a virus or rumour through a network. The name “Firefighter” arises from the initial analogy being the spread of fire among the vertices of a graph. Given a graph G, the process begins at time t = 0 when one or more vertices of G spontaneously “catch fire”. At each subsequent time step, a collection of b ≥ 1 “firefighters” defend a set of vertices which are not burning, and then the fire spreads from each burning vertex to all of its undefended neighbours. There are many possible objectives one could have, for example minimizing the expected number of vertices burned when the fire breaks out at a random location or locations, finding the maximum number of vertices that can be saved from burning if the fire breaks out at known locations, minimizing the length of the process, or bounding the proportion of vertices that can be saved from burning. It is also possible to consider multiple objectives that may be in conflict. There are a great number of papers in the literature which address these, and other, issues in terms of computational complexity, algorithms, approximation, asymptotics, heuristics, and more. The main purpose of this thesis is to survey developments on Firefighter and its variants which have appeared in the literature subsequent to a previous survey that appeared in 2009 [S. Finbow and G. MacGillivray. The firefighter problem: A survey of results, directions and questions. Australas. J. Comb., 43, 2009]. The thesis concludes with a list of open problems and future directions from the previous survey, annotated with references for papers that have made progress on those topics since then. en_US
dc.language English eng
dc.language.iso en en_US
dc.rights Available to the World Wide Web en_US
dc.subject Firefighter en_US
dc.subject Surviving Rate en_US
dc.subject Complexity en_US
dc.subject Graph Theory en_US
dc.title A new survey on the firefighter problem en_US
dc.type Thesis en_US
dc.contributor.supervisor MacGillivray, Gary
dc.contributor.supervisor Mynhardt, Kieka
dc.degree.department Department of Mathematics and Statistics en_US
dc.degree.level Master of Science M.Sc. en_US
dc.description.scholarlevel Graduate en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UVicSpace


My Account