Surviving rate of graphs and Firefighter Problem  

作　　者：Weifan WANG Jiangxu KONG 

机构地区：[1]Department of Mathematics,Zhejiang Normal University,Jinhua 321004,China

出　　处：《Frontiers of Mathematics in China》2022年第2期227-254,共28页中国高等学校学术文摘·数学（英文）

基　　金：supported by the National Natural Science Foundation of China(No.12031018);The second author was supported by China Postdoctoral Science Foundation(2020M681927);the Fundamental Research Funds for the Provincial Universities of Zhejiang(2021YW08).

摘　　要：The Firefighter Problem on a graph can be viewed as a simplified model of the spread of contagion,fire,rumor,computer virus,etc.The fire breaks out at one or more vertices in a graph at the first round,and the firefighter chooses some vertices to protect.The fire spreads to all non-protected neighbors at the beginning of each time-step.The process stops when the fire can no longer spread.The Firefighter Problem has attracted considerable attention since it was introduced in 1995.In this paper we provide a survey on recent research progress of this field,including algorithms and complexity,Firefighter Problem for special graphs(finite and infinite)and digraphs,surviving rate and burning number of graphs.We also collect some open problems and possible research subjects.

关 键 词：GRAPH network Firefighter Problem surviving rate burning number 

分 类 号：O17[理学—数学]