.png){kind=icon}
.png){kind=icon}
Return
Exact Solutions for the Moving Firefighter Problem on Trees
.png){kind=icon}
PRE
AI
DOI：10.1002/net.70037.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The moving firefighter problem (MFP) is a more realistic variant of the classic firefighter problem (FP), where firefighters require time for both travel and defense. Unfortunately, the only known exact solution for the MFP does not scale. In this paper, we establish that the MFP is NP-complete on trees of maximum degree three and present four alternative methods to find exact solutions for the case of arbitrary trees with a single initial fire and one firefighter. The first method is a dynamic programming algorithm, while the other three methods are based on mathematical programming: an integer quadratically constrained program (IQCP), and two distinct integer linear programs (ILP and E-ILP). Our mathematical programming formulations exploit the inherent properties of tree topologies to significantly improve scalability by reducing the number of decision variables and constraints relative to those for arbitrary graphs. We present a comprehensive experimental analysis of the performance and scalability of the proposed solutions.
Keywords:
dynamic programming
firefighter problem
integer programming
NP-hardness
quadratic programming
spread and containment in networks
Journal
N
IF:
1.3
Papers:
49
Citations:
3.4K