Article ID Journal Published Year Pages File Type
4650832 Discrete Mathematics 2007 12 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The firefighter problem for graphs of maximum degree three
Authors
, , , ,