The search functionality is under construction.

The search functionality is under construction.

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 (*k* children. In case of ternary trees, *k*=3 and thus the approximation ratio satisfies

- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.196-199

- Publication Date
- 2011/02/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.E94.D.196

- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)

- Category

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 (*k* children. In case of ternary trees, *k*=3 and thus the approximation ratio satisfies

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 (*k* children. In case of ternary trees, *k*=3 and thus the approximation ratio satisfies

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 (*k* children. In case of ternary trees, *k*=3 and thus the approximation ratio satisfies

ER -