The firefighter problem for cubic graphs |
| |
Authors: | Andrew King |
| |
Institution: | a Department of Computer Science, McGill University, Canada b Department of Mathematics and Statistics, University of Victoria, Canada |
| |
Abstract: | We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two. |
| |
Keywords: | Firefighter problem Dichotomy theorem |
本文献已被 ScienceDirect 等数据库收录! |
|