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