MMM
YYYY
Surviving rate of graphs and Firefighter Problem
图的存活率和消防员问题
グラフの生存率と消防士の問題
그래프의 생존율과 소방관 문제
Tasa de supervivencia de gráficos y problema de bombero
Taux de survie des graphiques et problème de pompier
Скорость выживания графов и проблема пожарного
Weifan WANG 王维凡, Jiangxu KONG 孔将旭
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China
中国 金华 浙江师范大学数学系
Frontiers of Mathematics in China, 15 April 2022
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.
Frontiers of Mathematics in China_1
Frontiers of Mathematics in China_2
Reviews and Discussions
https://www.hotpaper.io/index.html
Phase reconstruction via metasurface-integrated quantum analog operation
Tunable vertical cavity microlasers based on MAPbI₃ phase change perovskite
Light-induced enhancement of exciton transport in organic molecular crystal
Double topological phase singularities in highly absorbing ultra-thin film structures for ultrasensitive humidity sensing
Soliton microcombs in optical microresonators with perfect spectral envelopes
Spin-dependent amplitude and phase modulation with multifold interferences via single-layer diatomic all-silicon metasurfaces
Highly sensitive laser spectroscopy sensing based on a novel four-prong quartz tuning fork
A novel approach towards robust construction of physical colors on lithium niobate crystal
Multi-photon neuron embedded bionic skin for high-precision complex texture and object reconstruction perception research
Single-beam optical trap-based surface-enhanced raman scattering optofluidic molecular fingerprint spectroscopy detection system
High-frequency enhanced ultrafast compressed active photography
Efficient generation of vectorial terahertz beams using surface-wave excited metasurfaces



Previous Article                                Next Article
About
|
Contact
|
Copyright © Hot Paper