2011 | OriginalPaper | Buchkapitel
Parameterized Complexity of the Firefighter Problem
verfasst von : Cristina Bazgan, Morgan Chopin, Michael R. Fellows
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we study the parameterized complexity of the firefighter problem. More precisely, we show that
Saving
k
-Vertices
and its dual
Saving All But
k
-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,
Saving
k
-Vertices
is fixed-parameter tractable on planar graphs for parameter
k
. Moreover, we prove a lower bound to polynomial kernelization for
Saving All But
k
-Vertices
.