Improved Approximation Algorithms for Firefighter Problem on Trees.

Yutaka Iwaikawa Naoyuki Kamiyama Tomomi Matsui

Published in: IEICE Trans. Inf. Syst. (2011)

Keyphrases

approximation algorithms
np hard
special case
vertex cover
facility location problem
worst case
minimum cost
randomized algorithms
primal dual
decision trees
approximation ratio
approximation schemes
open shop
disjoint paths
np hardness
exact algorithms
constant factor
genetic algorithm