Skip to main content

FRAMES logo
Resource Catalog

Document

Type: Journal Article
Author(s): Pierre Coupechoux; Marc Demange; David Ellison; Bertrand Jouve
Publication Date: 2019

In the Firefighter problem, introduced by Hartnell in 1995, a fire spreads through a graph while a player chooses which vertices to protect in order to contain it. In this paper, we focus on the case of trees and we consider as well the Fractional Firefighter game where the amount of protection allocated to a vertex lies between 0 and 1. While most of the work in this area deals with a constant amount of firefighters available at each turn, we consider three research questions which arise when including the sequence of firefighters as part of the instance. We first introduce the online version of both Firefighter and Fractional Firefighter, in which the number of firefighters available at each turn is revealed over time. We show that a greedy algorithm on finite trees is 1/2-competitive for both online versions, which generalises a result previously known for special cases of Firefighter. We also show that the optimal competitive ratio of online Firefighter ranges between 1/2 and the inverse of the golden ratio. Next, given two firefighter sequences, we discuss sufficient conditions for the existence of an infinite tree that separates them, in the sense that the fire can be contained with one sequence but not with the other. To this aim, we study a new purely numerical game called targeting game. Finally, we give sufficient conditions for the fire to be contained, expressed as the asymptotic comparison of the number of firefighters and the size of the tree levels.

Online Links
Citation: Coupechoux, Pierre; Demange, Marc; Ellison, David; Jouve, Bertrand. 2019. Firefighting on trees. Theoretical Computer Science 794:69-84.

Cataloging Information

Topics:
Regions:
Alaska    California    Eastern    Great Basin    Hawaii    Northern Rockies    Northwest    Rocky Mountain    Southern    Southwest    International    National
Keywords:
  • fire spread
  • firefighter problem
  • firefighting
  • graph theory
  • optimization
  • resource management
Record Last Modified:
Record Maintained By: FRAMES Staff (https://www.frames.gov/contact)
FRAMES Record Number: 57450