Paper Info
Title
Parameterized complexity of the firefighter problem
Abstract
In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that Savingk-Vertices and its dual Saving All Butk-Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Savingk-Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All Butk-Vertices.
Year
DOI
Venue
2011
10.1007/978-3-642-25591-5_66
ISAAC
Keywords
DocType
Volume
fixed-parameter tractable,parameter k,bipartite graph,firefighter problem,planar graph,parameterized complexity,Parameterized complexity
Conference
7074
ISSN
Citations 
PageRank 
0302-9743
3
0.44
References 
Authors
9
3
Name
Order
Citations
PageRank
Cristina Bazgan167962.76
Morgan Chopin2856.78
Michael R. Fellows34138319.37