Parameterized complexity of firefighting

DOI10.1016/J.JCSS.2014.03.001MaRDI QIDQ2453548zbMATH OpenOpenAlexWikidataFDO

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

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

kernelizationfirefighter problemfixed parameter tractability

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)

Recommendations

• Parameterized Complexity of Firefighting Revisited
• Parameterized complexity of the firefighter problem
• The firefighter problem on graph classes

Cites work

• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• scientific article; zbMATH DE number 1506515 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Cross-composition: a new technique for kernelization lower bounds
• Diameter and treewidth in minor-closed graph families
• Easy problems for tree-decomposable graphs
• Editing graphs to satisfy degree constraints: a parameterized approach
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• On problems without polynomial kernels
• Parameterized Complexity of Firefighting Revisited
• Parameterized complexity of the firefighter problem
• Strong computational lower bounds via parameterized complexity
• The Firefighter problem: a survey of results, directions and questions
• The firefighter problem for graphs of maximum degree three
• The firefighter problem with more than one firefighter on trees
• Towards more efficient infection and fire fighting

Cited in

(13)

• Politician’s Firefighting
• Firefighting on trees
• Fractals for kernelization lower bounds
• Saving critical nodes with firefighters is FPT
• The firefighter problem on graph classes
• New integrality gap results for the firefighters problem on trees
• The unfortunate-flow problem
• The Firefighter Problem: A Structural Analysis
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• Parameterized Complexity of Firefighting Revisited
• Firefighting as a strategic game
• The firefighter problem: further steps in understanding its complexity
• Parameterized complexity of the firefighter problem

This page was built for publication: Parameterized complexity of firefighting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453548)