Parameterized complexity of firefighting

DOI10.1016/j.jcss.2014.03.001zbMath1411.68046OpenAlexW2064408514WikidataQ57359593 ScholiaQ57359593MaRDI QIDQ2453548

Erik Jan van Leeuwen, Michael R. Fellows, Fedor V. Fomin, Morgan Chopin, Cristina Bazgan, Marek Cygan

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.03.001

zbMATH Keywords

fixed parameter tractabilitykernelizationfirefighter problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

The Firefighter Problem: A Structural Analysis ⋮ The firefighter problem on graph classes ⋮ Unnamed Item ⋮ New Integrality Gap Results for the Firefighters Problem on Trees ⋮ Fractals for Kernelization Lower Bounds ⋮ The firefighter problem: further steps in understanding its complexity ⋮ On structural parameterizations of firefighting ⋮ Firefighting on trees ⋮ Firefighting as a Strategic Game ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• Strong computational lower bounds via parameterized complexity
• On problems without polynomial kernels
• Diameter and treewidth in minor-closed graph families
• The firefighter problem with more than one firefighter on trees
• The firefighter problem for graphs of maximum degree three
• TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING
• Parameterized Complexity of Firefighting Revisited
• Parameterized Complexity of the Firefighter Problem
• Easy problems for tree-decomposable graphs
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Parameterized complexity of firefighting