| Autor: |
Burgess, Andrea C., Hawkin, John, Howse, Alexander, Marcoux, John, Pike, David A. |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. In $\textit{distance-restricted firefighting}$ 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 $b$-Firefighter even on bipartite graphs and present an integer program for computing the exact value. We also discuss some interesting properties of the $\textit{Expected Damage}$ function. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
