a Department of Mathematics and Statistics, University of Victoria, Victoria, BC, Canada b Department of Telecommunications and Informatics, University of Trento, Trento, Italy
Abstract:
We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.