Distance-Restricted Firefighting on Finite Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916883494600704 |
|---|---|
| author | Burgess, Andrea C. Hawkin, John Howse, Alexander Marcoux, John Pike, David A. |
| author_facet | Burgess, Andrea C. Hawkin, John Howse, Alexander Marcoux, John Pike, David A. |
| contents | 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 unburned neighbourhood of all the burning vertices and the firefighters again protect $b$ vertices. Once a vertex has been burned 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 {\sc $b$-Firefighter} and present an integer program for computing the exact value. We also discuss some interesting properties of the \textit{Expected Damage} function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_12575 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Distance-Restricted Firefighting on Finite Graphs Burgess, Andrea C. Hawkin, John Howse, Alexander Marcoux, John Pike, David A. Combinatorics 05c57 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 unburned neighbourhood of all the burning vertices and the firefighters again protect $b$ vertices. Once a vertex has been burned 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 {\sc $b$-Firefighter} and present an integer program for computing the exact value. We also discuss some interesting properties of the \textit{Expected Damage} function. |
| title | Distance-Restricted Firefighting on Finite Graphs |
| topic | Combinatorics 05c57 |
| url | https://arxiv.org/abs/2306.12575 |