
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Improved Approximation Algorithms for Firefighter Problem on Trees
Yutaka IWAIKAWA Naoyuki KAMIYAMA Tomomi MATSUI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E94D
No.2
pp.196199 Publication Date: 2011/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E94.D.196
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science  Mathematical Foundations and Applications of Algorithms and Computer Science ) Category: Keyword: firefighter problem, approximation algorithm, rooted tree,
Full Text: PDF(184.9KB) >>Buy this Article
Summary:
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 NPhard 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 ()approximation algorithm, we obtain approximation algorithm when a root has k children. In case of ternary trees, k=3 and thus the approximation ratio satisfies ≥ 0.6892, which improves the existing result ≥ 0.6321. Second technique is based on backward induction and improves an approximation algorithm for firefighter problem on ternary trees. If we apply the technique to existing () approximation algorithm, we obtain 0.6976approximation algorithm. Lastly, we combine the above two techniques and obtain 0.7144approximation algorithm for firefighter problem on ternary trees.

