All reports by Author Morgan Chopin:

__
TR13-162
| 1st October 2013
__

Janka ChlebĂkovĂˇ, Morgan Chopin#### The Firefighter Problem: A Structural Analysis

Revisions: 1

Janka ChlebĂkovĂˇ, Morgan Chopin

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget ... more >>>