Parameterized complexity of firefighting
DOI10.1016/J.JCSS.2014.03.001zbMATH Open1411.68046OpenAlexW2064408514WikidataQ57359593 ScholiaQ57359593MaRDI QIDQ2453548FDOQ2453548
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
Recommendations
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)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On problems without polynomial kernels
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- The firefighter problem with more than one firefighter on trees
- The firefighter problem for graphs of maximum degree three
- The Firefighter problem: a survey of results, directions and questions
- Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
- Editing graphs to satisfy degree constraints: a parameterized approach
- Title not available (Why is that?)
- Strong computational lower bounds via parameterized complexity
- Diameter and treewidth in minor-closed graph families
- Cross-composition: a new technique for kernelization lower bounds
- Parameterized Complexity of Firefighting Revisited
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards more efficient infection and fire fighting
- Parameterized complexity of the firefighter problem
Cited In (14)
- Firefighting on trees
- Politician’s Firefighting
- Parameterized Complexity of Firefighting Revisited
- Parameterized complexity of the firefighter problem
- New integrality gap results for the firefighters problem on trees
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Firefighting as a strategic game
- The Firefighter Problem: A Structural Analysis
- The firefighter problem on graph classes
- On structural parameterizations of firefighting
- Saving critical nodes with firefighters is FPT
- The unfortunate-flow problem
- Fractals for kernelization lower bounds
- The firefighter problem: further steps in understanding its complexity
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)