(Peer-Reviewed) Surviving rate of graphs and Firefighter Problem
Weifan WANG 王维凡, Jiangxu KONG 孔将旭
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China
中国 金华 浙江师范大学数学系
Abstract
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 fire-fighter 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, Fire-fighter 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.
Integrated metasurface-freeform system enabled multi-focal planes augmented reality display
Shifei Zhang, Lina Gao, Yidan Zhao, Yongdong Wang, Bo Wang, Junjie Li, Jiaxi Duan, Dewen Cheng, Cheng-Wei Qiu, Yongtian Wang, Tong Yang, Lingling Huang
Opto-Electronic Science
2026-01-23
