Distance-Restricted Firefighting on Finite Graphs

arXiv2306.12575MaRDI QIDQ6441071FDOQ6441071

Authors: Andrea Burgess, John Hawkin, Alexander Howse, John Marcoux, David A. Pike 

Publication date: 21 June 2023

Abstract: In the classic version of the game of firefighter, on the first turn a fire breaks out on a vertex in a graph $G$ and then $b$ firefighters protect $b$ vertices. On each subsequent turn, the fire spreads to the collective unburnt neighbourhood of all the burning vertices and the firefighters again protect $b$ vertices. Once a vertex has been burnt or protected it remains that way for the rest of the game. We previously introduced the concept of $extitdistance-restrictedfirefighting$ where the firefighters' movement is restricted so they can only move up to some fixed distance $d$ and they may or may not be permitted to move through burning vertices. In this paper we establish the NP-Completeness of the distance-restricted versions of the $extitMaximumVerticesSaved$ problem and present an integer program for solving these problems. In the penultimate section we also discuss some interesting properties of the $extitExpectedDamage$ function.

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57)

This page was built for publication: Distance-Restricted Firefighting on Finite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441071)