Indexed by:
Abstract:
The classical firefighter problem, introduced by Bert Hartnell in 1995, is a deterministic discrete-time model of the spread and defence of fire, rumor, or disease. In contrast to the generally "discontinuous" firefighter movements of the classical setting, we propose in the paper the continuous firefighting model. Given an undirected graph G, at time 0, all vertices of G are undefended, and fires break out on one or multiple different vertices of G. At each subsequent time step, the fire spreads from each burning vertex to all of its undefended neighbors. A finite number of firefighters are available to be assigned on some vertices of G at time 1, and each firefighter can only move from his current location (vertex) to one of his neighbors or stay still at each time step. A vertex is defended if some firefighter reaches it no later than the fire. We study fire containment on infinite k-dimensional square grids under the continuous firefighting model. We show that the minimum number of firefighters needed is exactly 2k for single fire, and 5 for multiple fires when k = 2.
Keyword:
Reprint Author's Address:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017)
ISSN: 0302-9743
Year: 2017
Volume: 10185
Page: 157-170
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: