• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Chen, Xujin (Chen, Xujin.) | Hu, Xiaodong (Hu, Xiaodong.) | Wang, Changjun (Wang, Changjun.) | Zhang, Ying (Zhang, Ying.)

Indexed by:

CPCI-S EI Scopus

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:

Continuous firefighting Infinite square grids Firefighter problem Fire containment

Author Community:

  • [ 1 ] [Chen, Xujin]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 2 ] [Hu, Xiaodong]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 3 ] [Zhang, Ying]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 4 ] [Wang, Changjun]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing, Peoples R China

Reprint Author's Address:

  • [Zhang, Ying]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

Show more details

Related Keywords:

Related Article:

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:

Online/Total:695/5574214
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.