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
基金
加拿大自然科学与工程研究理事会;
关键词
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