Home >

news Help

Publication Information


Title
Japanese: 
English:Improved Approximation Algorithms for Firefighter Problem on Trees 
Author
Japanese: IWAIKAWA Yutaka, KAMIYAMA Naoyuki, 松井知己.  
English: IWAIKAWA Yutaka, KAMIYAMA Naoyuki, MATSUI Tomomi.  
Language English 
Journal/Book name
Japanese: 
English:IEICE Transactions on Information and Systems 
Volume, Number, Page Vol. 94    No. 2    pp. 196-199
Published date Aug. 2013 
Publisher
Japanese: 
English:The Institute of Electronics, Information and Communication Engineers 
Conference name
Japanese: 
English: 
Conference site
Japanese: 
English: 
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 (1-1/e)-approximation algorithm, we obtain $(1- {k-1 \\over (k-1)e + 1})$-approximation algorithm when a root has k children. In case of ternary trees, k=3 and thus the approximation ratio satisfies $(1- {k-1 \\over (k-1)e + 1})$ ≥ 0.6892, which improves the existing result 1-1/e ≥ 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 (1-1/e)-approximation algorithm, we obtain 0.6976-approximation algorithm. Lastly, we combine the above two techniques and obtain 0.7144-approximation algorithm for firefighter problem on ternary trees.

©2007 Tokyo Institute of Technology All rights reserved.