• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

The firefighter problem with more than one firefighter on trees

Thumbnail
Date
2013
Link to item file
https://arxiv.org/abs/1110.0341v1
Dewey
Recherche opérationnelle
Sujet
Firefighter problem; Caterpillars; Complexity; Trees; Approximation
Journal issue
Discrete Applied Mathematics
Volume
161
Number
7-8
Publication date
2013
Article pages
899-908
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2012.11.011
URI
https://basepub.dauphine.fr/handle/123456789/11458
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chopin, Morgan
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.