Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorChopin, Morgan
dc.contributor.authorCygan, Marek
dc.contributor.authorFellows, Michael R.
dc.contributor.authorFomin, Fedor V.
dc.contributor.authorvan Leeuwen, Erik Jan
dc.date.accessioned2014-02-14T09:31:10Z
dc.date.available2014-02-14T09:31:10Z
dc.date.issued2014
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12671
dc.language.isoenen
dc.subjectFirefighter problem
dc.subjectBipartite graphs
dc.subject.ddc519en
dc.titleParameterized Complexity of Firefighting
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDepartment of Informatics, University of Bergen;Norvège
dc.contributor.editoruniversityotherCharles Darwin University,Darwin;Australie
dc.contributor.editoruniversityotherUniversity of Warsaw, Warsaw;Pologne
dc.description.abstractenTheFirefighterproblem is to place firefighters on the vertices ofa graph to prevent a fire with known starting point from lighting upthe entire graph. In each time step, a firefighter may be placed on anunburned vertex, permanently protecting it, and the fire spreads toall neighboring unprotected vertices of burning vertices. The goal isto let as few vertices burn as possible. This problem is known to beNP-complete, even when restricted to trees of maximum degree three.Initial study showed theFirefighterproblem to be fixed-parametertractable on trees in various parameterizations. In this paper, wecon-sider a generalization of this problem, where at each time stepb≥1firefighters can be deployed. Our results answer several open questionsraised by Cai et al. [8]. We show that this problem is W[1]-hard whenparameterized by the number of saved vertices, protected vertices, andburned vertices. We also investigate several combined parameteriza-tions for which the problem is fixed-parameter tractable. Some of ouralgorithms improve on previously known algorithms. We also establishlower bounds to polynomial kernelization
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol80
dc.relation.isversionofjnlissue7
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages1285-1297
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.jcss.2014.03.001
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-04-13T08:25:39Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds82043*
hal.person.labIds36796*
hal.person.labIds63727*
hal.person.labIds36796*
hal.faultCode{"duplicate-entry":{"hal-01505557":{"doi":"1.0"}}}


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record