Show simple item record

dc.contributor.authorBazgan, Cristina*
dc.contributor.authorChopin, Morgan*
dc.contributor.authorRies, Bernard*
dc.date.accessioned2013-06-21T11:00:16Z
dc.date.available2013-06-21T11:00:16Z
dc.date.issued2013
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11458
dc.language.isoenen
dc.subjectFirefighter problem
dc.subjectCaterpillars
dc.subjectComplexity
dc.subjectTrees
dc.subjectApproximation
dc.subject.ddc003en
dc.titleThe firefighter problem with more than one firefighter on trees
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max(S,b)(S,b)-Fire where b≥2b≥2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to SS. We also study the related decision problem (S,b)(S,b)-Fire that asks whether all the vertices in SS can be saved using b≥2b≥2 firefighters at each time step.We show that (S,b)(S,b)-Fire is NP-complete for trees of maximum degree b+2b+2 even when SS is the set of leaves. Using this last result, we prove the NP-hardness of Max(S,b)(S,b)-Fire for trees of maximum degree b+3b+3 even when SS is the set of all vertices. On the positive side, we give a polynomial-time algorithm for solving (S,b)(S,b)-Fire and Max(S,b)(S,b)-Fire on trees of maximum degree b+2b+2 when the fire breaks out at a vertex of degree at most b+1b+1. Moreover, we present a polynomial-time algorithm for the Max(S,b)(S,b)-Fire problem (and the corresponding weighted version) for a subclass of trees, namely kk-caterpillars. Finally, we observe that the minimization version of Max(S,b)(S,b)-Fire is not n1−εn1−ε-approximable on trees for any ϵ∈(0,1)ϵ∈(0,1) and b≥1b≥1 if P≠NPP≠NP.
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol161
dc.relation.isversionofjnlissue7-8
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages899-908
dc.relation.isversionofdoi10.1016/j.dam.2012.11.011
dc.identifier.urlsitehttps://arxiv.org/abs/1110.0341v1
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-23T09:31:22Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01505574*


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