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
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
High-efficiency RGB achromatic liquid crystal diffractive optical elements
On-chip light control of semiconductor optoelectronic devices using integrated metasurfaces
Ferroelectric domain engineering of lithium niobate
Smart reconfigurable metadevices made of shape memory alloy metamaterials
Direct detection with an optimal transfer function: toward the electrical spectral efficiency of coherent homodyne detection



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