Firefighting multiple disease outbreaks under different defence policies

Variations of the Firefighter problem offer deterministic, discrete time models for disease control. Classic Firefighter (CF) offers a model for disease control using vaccination. In the first section of the thesis, we review the literature, compare CF to a related graph problem and present some results on extremal graphs. We then introduce a polynomial time algorithm for optimal solutions of certain instances of CF. In the next section, we introduce the Edge-Defence Firefighter Problem (EDF), which models disease control via contact reduction. We present some results on its properties and on how certain results on CF can be translated into EDF results. We present polynomial heuristic algorithms for EDF defence strategies on both finite and infinite square grids. We derive an Integer Program (IP) for EDF, along with results on valid inequalities that can be used to speed up the calculation time. Finally in this section, we present computational results on several heuristics for EDF defence strategies, derived from our CF algorithm. In the final chapter, we introduce the Cost-Value Firefighter Problem (CVF) and the Distance-Limited Firefighter Problem (DLF). Both variations are based on CF. In CVF, we assume that vertices can have different costs and values to vaccinate, modelling the logistics of vaccinating interconnected population centres of varying size. In DLF, we relax the assumption in CF that defenders can travel an arbitrary distance between vertices they defend, instead fixing a maximum distance defenders can travel between time steps. We present various IP formulations for both, along with valid inequalities and computational results. Finally, we present polynomial time algorithms for DLF on paths.