Title of article :
The firefighter problem for graphs of maximum degree three Original Research Article
Author/Authors :
Stephen Finbow، نويسنده , , Andrew King، نويسنده , , Gary MacGillivray، نويسنده , , Romeo Rizzi، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
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 :
Firefigher problem , Optimization on graphs , NP-complete problem
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics
