Alexander J. M. Howse

dblp:135/0567 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
1since 2021 · last 2026
0000-0001-9977-6092ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 since 2021
YearPublicationVenuePosition
2026 Distance-restricted firefighting on finite graphs
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 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 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 and present an integer program for computing the exact value. We also discuss some interesting properties of the Expected Damage function.
Andrea C. Burgess, John Hawkin, Alexander J. M. Howse, John Marcoux, David A. Pike
Theor. Comput. Sci.3