Premium
The Firefighter problem: Saving sets of vertices on cubic graphs
Author(s) -
Duffy Christopher,
MacGillivray Gary
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21873
Subject(s) - combinatorics , vertex (graph theory) , degree (music) , graph , mathematics , context (archaeology) , computer science , independent set , set (abstract data type) , discrete mathematics , physics , geography , archaeology , acoustics , programming language
In the context of the Firefighter problem, a deterministic model of the spread of a fire or virus on a graph, SFIRE is the decision problem that asks if a specified set of vertices can be prevented from burning. We show SFIRE remains NP‐complete even when restricted to graphs with maximum degree 3 even when the fire starts at a vertex of degree 2.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom