User:Giematt/sandbox

This is the user sandbox of Giematt. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here.

Other sandboxes: Main sandbox | Template sandbox

Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

The firefighter problem is a computational problem first introduced by Bert Hartnell in 1995. The problem takes place on a graph G where at the beginning one vertex is considered burning. At each interval of time, the firefighter defends a vertex, while the fire spreads and causes all undefended vertices that are adjacent to any burning one to be burning as well. All burning and defended vertices remain in their state for the rest of the scenario. The goal is to have as many non-burning vertices, or saved vertices, as possible by the time that the fire can no longer spread.

The firefighter problem is known to be NP-complete for bipartite graphs. Many variants on the problem have been proposed and studied, such as those involving multiple firefighters or those with different goals such as saving a specific set of vertices or simply preventing the fire from spreading further in as few intervals as possible. It has been suggested that this problem may be of relevance in handling epidemics.