The Firefighter problem: Saving sets of vertices on cubic graphs

被引：1
作者：
Duffy, Christopher [1 ]
MacGillivray, Gary [2 ]
机构：
[1] Univ Saskatchewan, Dept Math & Stat, Saskatoon, SK S7N 5E6, Canada
[2] Univ Victoria, Dept Math & Stat, Victoria, BC, Canada
来源：
NETWORKS | 2019年 / 74卷 / 01期
关键词：
algorithms; complexity; discrete-time process; Firefighter; graph process; graph theory; SURVIVING RATE; BURN;
D O I：
10.1002/net.21873
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the context of the Firefighter problem, a deterministic model of the spread of a fire or virus on a graph, SFIRE is the decision problem that asks if a specified set of vertices can be prevented from burning. We show SFIRE remains NP-complete even when restricted to graphs with maximum degree 3 even when the fire starts at a vertex of degree 2.
引用
收藏
页码：62 / 69
页数：8
相关论文
共 27 条
  • [1] [Anonymous], THESIS
  • [2] [Anonymous], 1995, P 25 MAN C COMB MATH
  • [3] Approximability of the Firefighter Problem Computing Cuts over Time
    Anshelevich, Elliot
    Chakrabarty, Deeparnab
    Hate, Ameya
    Swamy, Chaitanya
    [J]. ALGORITHMICA, 2012, 62 (1-2) : 520 - 536
  • [4] Anshelevich E, 2009, LECT NOTES COMPUT SC, V5878, P974, DOI 10.1007/978-3-642-10631-6_98
  • [5] Parameterized complexity of firefighting
    Bazgan, Cristina
    Chopin, Morgan
    Cygan, Marek
    Fellows, Michael R.
    Fomin, Fedor V.
    van Leeuwen, Erik Jan
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2014, 80 (07) : 1285 - 1297
  • [6] The firefighter problem with more than one firefighter on trees
    Bazgan, Cristina
    Chopin, Morgan
    Ries, Bernard
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (7-8) : 899 - 908
  • [7] Bounds on the burning number
    Bessy, Stephane
    Bonato, Anthony
    Janssen, Jeannette
    Rautenbach, Dieter
    Roshanbin, Elham
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 235 : 16 - 22
  • [8] How to Burn a Graph
    Bonato, Anthony
    Janssen, Jeannette
    Roshanbin, Elham
    [J]. INTERNET MATHEMATICS, 2016, 12 (1-2) : 85 - 100
  • [9] Bondy J.A., 2008, GTM
  • [10] SURVIVING RATES OF GRAPHS WITH BOUNDED TREEWIDTH FOR THE FIREFIGHTER PROBLEM
    Cai, Leizhen
    Cheng, Yongxi
    Verbin, Elad
    Zhou, Yuan
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1322 - 1335
123