dc.contributor.author Bazgan, Cristina * dc.contributor.author Chopin, Morgan * dc.contributor.author Ries, Bernard * dc.date.accessioned 2013-06-21T11:00:16Z dc.date.available 2013-06-21T11:00:16Z dc.date.issued 2013 dc.identifier.issn 0166-218X dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/11458 dc.language.iso en en dc.subject Firefighter problem dc.subject Caterpillars dc.subject Complexity dc.subject Trees dc.subject Approximation dc.subject.ddc 003 en dc.title The firefighter problem with more than one firefighter on trees dc.type Article accepté pour publication ou publié dc.description.abstracten In 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.isversionofjnlname Discrete Applied Mathematics dc.relation.isversionofjnlvol 161 dc.relation.isversionofjnlissue 7-8 dc.relation.isversionofjnldate 2013 dc.relation.isversionofjnlpages 899-908 dc.relation.isversionofdoi 10.1016/j.dam.2012.11.011 dc.identifier.urlsite https://arxiv.org/abs/1110.0341v1 dc.relation.isversionofjnlpublisher Elsevier dc.subject.ddclabel Recherche opérationnelle en dc.relation.forthcoming non en dc.relation.forthcomingprint non en dc.description.ssrncandidate non dc.description.halcandidate oui dc.description.readership recherche dc.description.audience International dc.relation.Isversionofjnlpeerreviewed oui dc.date.updated 2017-01-23T09:31:22Z hal.person.labIds 989 * hal.person.labIds 989 * hal.person.labIds 989 * hal.identifier hal-01505574 *
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.