The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing (
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yutaka IWAIKAWA, Naoyuki KAMIYAMA, Tomomi MATSUI, "Improved Approximation Algorithms for Firefighter Problem on Trees" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 196-199, February 2011, doi: 10.1587/transinf.E94.D.196.
Abstract: The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing (
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.196/_p
Copy
@ARTICLE{e94-d_2_196,
author={Yutaka IWAIKAWA, Naoyuki KAMIYAMA, Tomomi MATSUI, },
journal={IEICE TRANSACTIONS on Information},
title={Improved Approximation Algorithms for Firefighter Problem on Trees},
year={2011},
volume={E94-D},
number={2},
pages={196-199},
abstract={The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing (
keywords={},
doi={10.1587/transinf.E94.D.196},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Improved Approximation Algorithms for Firefighter Problem on Trees
T2 - IEICE TRANSACTIONS on Information
SP - 196
EP - 199
AU - Yutaka IWAIKAWA
AU - Naoyuki KAMIYAMA
AU - Tomomi MATSUI
PY - 2011
DO - 10.1587/transinf.E94.D.196
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2011
AB - The firefighter problem is used to model the spread of fire, infectious diseases, and computer viruses. This paper deals with firefighter problem on rooted trees. It is known that the firefighter problem is NP-hard even for rooted trees of maximum degree 3. We propose techniques to improve a given approximation algorithm. First, we introduce an implicit enumeration technique. By applying the technique to existing (
ER -