The firefighter problem for graphs of maximum degree three

被引：80
作者：
Finbow, Stephen [1 ]
King, Andrew
MacGillivray, Gary
Rizzi, Romeo
机构：
[1] Univ Victoria, Dept Math & Stat, Victoria, BC, Canada
[2] Univ Trent, Dept Telecommun & Informat, Trento, Italy
来源：
DISCRETE MATHEMATICS | 2007年 / 307卷 / 16期
基金：
加拿大自然科学与工程研究理事会;
关键词：
firefigher problem; NP-complete problem; optimization on graphs;
D O I：
10.1016/j.disc.2005.12.053
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：2094 / 2105
页数：12
相关论文
共 11 条
[1]  
Carey M., 1979, COMPUTER INTRACTABIL
[2]   ON DESIGNING A NETWORK TO DEFEND AGAINST RANDOM ATTACKS OF RADIUS 2 [J].
FINBOW, AS ;
HARTNELL, BL .
NETWORKS, 1989, 19 (07) :771-792
[3]  
Finbow S., 2000, Journal of Combinatorial Mathematics and Combinatorial Computing, V33, P311
[4]  
Fogarty P, 2003, THESIS U VERMONT US
[5]  
Gunther G., 1990, C NUMER, V79, P69
[6]  
Hartnell B., 1995, 24 MAN C COMB MATH C
[7]  
Hartnell B., 2000, C NUMER, V145, P187
[8]   ON MINIMAL NEIGHBORHOOD-CONNECTED GRAPHS [J].
HARTNELL, BL ;
KOCAY, W .
DISCRETE MATHEMATICS, 1991, 92 (1-3) :95-105
[9]  
MacGillivray G., 2003, Journal of Combinatorial Mathematics and Combinatorial Computing, V47, P83
[10]  
MOELLER SA, 2002, J COMBIN MATH COMBIN, V41, P19
12