• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Parameterized Complexity of the Firefighter Problem

Bazgan, Cristina; Chopin, Morgan; Fellows, Michael R. (2011), Parameterized Complexity of the Firefighter Problem, in Watanabe, Osamu, ISAAC 2011, Springer : Berlin Heidelberg, p. 643-652

Type
Communication / Conférence
Date
2011
Conference country
JAPAN
Book title
ISAAC 2011
Book author
Watanabe, Osamu
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-25590-8
Pages
643-652
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Chopin, Morgan
Fellows, Michael R.
Abstract (EN)
In 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.
Subjects / Keywords
bipartite graphs; trees; Firefighter problem; vertex

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Complexity of Firefighting 
    Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan (2014) Article accepté pour publication ou publié
  • Thumbnail
    The Robust Set Problem: Parameterized Complexity and Approximation 
    Bazgan, Cristina; Chopin, Morgan (2012) Communication / Conférence
  • Thumbnail
    Parameterized Approximability of Maximizing the Spread of Influence in Networks 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
  • Thumbnail
    Parameterized approximability of maximizing the spread of influence in networks 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Thumbnail
    The Complexity of Finding Harmless Individuals in Social Networks 
    Bazgan, Cristina; Chopin, Morgan (2014) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo