Parameterized Complexity of Firefighting Revisited

DOI10.1007/978-3-642-28050-4_2zbMath1352.68098arXiv1109.4729OpenAlexW1505332898WikidataQ60488508 ScholiaQ60488508MaRDI QIDQ2891334

Fedor V. Fomin, Marek Cygan, Erik Jan van Leeuwen

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.4729

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

The firefighter problem: empirical results on random graphs ⋮ A matheuristic for the firefighter problem on graphs ⋮ The firefighter problem on graph classes ⋮ Parameterized complexity of firefighting ⋮ Firefighting as a Strategic Game

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On problems without polynomial kernels
• Diameter and treewidth in minor-closed graph families
• The firefighter problem for graphs of maximum degree three
• TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING
• 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 Revisited