Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorChopin, Morgan
dc.contributor.authorFellows, Michael R.
dc.date.accessioned2012-04-24T11:17:43Z
dc.date.available2012-04-24T11:17:43Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9031
dc.descriptionLNCS n°7074
dc.language.isoenen
dc.subjectbipartite graphs
dc.subjecttrees
dc.subjectFirefighter problem
dc.subjectvertex
dc.subject.ddc519en
dc.titleParameterized Complexity of the Firefighter Problem
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherCharles Darwin University;Australie
dc.contributor.editoruniversityotherInstitut Universitaire de France;France
dc.description.abstractenIn 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.
dc.identifier.citationpages643-652
dc.relation.ispartoftitleISAAC 2011
dc.relation.ispartofeditorWatanabe, Osamu
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2011
dc.description.sponsorshipprivateouien
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-3-642-25590-8
dc.relation.confcountryJAPAN
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:01:45Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record