图的存活率与消防员问题

消防员问题可视为传染病、火灾、谣言、计算机病毒等传播的一个简化模型.假设一把火在一个图的某个点或多个点燃起,消防员选择若干个未着火的顶点进行防护,然后火蔓延到前一步着火点的未燃邻点.当火不再蔓延时整个过程结束.消防员问题自1995年提出以来引起了人们的广泛关注.本文简述了与消防员问题相关的最近研究进展,包括算法复杂性、无限图和有向图的消防员问题、图的存活率、图的燃烧数及一些有待于进一步研究的问题.

Surviving Rate of Graphs and Firefighter Problem

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 infinite graphs and digraphs,surviving rate and burning number of graphs.We also collect some open problems and possible research subjects.