Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm

DOI10.1007/978-3-540-92182-0_25zbMath1183.05077MaRDI QIDQ3596724

Lin Yang, Elad Verbin, Leizhen Cai

Publication date: 29 January 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92182-0_25

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Related Items

On structural parameterizations of firefighting, Firefighting as a Strategic Game, A matheuristic for the firefighter problem on graphs, On the firefighter problem with spreading vaccination for maximizing the number of saved nodes: the IP model and LP rounding algorithms, Slash and burn on graphs -- firefighting with general weights, The firefighter problem: empirical results on random graphs, The firefighter problem: further steps in understanding its complexity, The firefighter problem on graph classes, The firefighter problem with more than one firefighter on trees, Surviving rate of graphs and firefighter problem, Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment, Firefighting on trees, Approximation algorithms for the geometric firefighter and budget fence problems, Asymptotic surviving rate of trees with multiple fire sources, Approximability of the firefighter problem. Computing cuts over time, More fires and more fighters, Parameterized complexity of firefighting, Multi-layered planar firefighting, Parameterized Complexity of Firefighting Revisited, The Firefighter Problem: A Structural Analysis, New Integrality Gap Results for the Firefighters Problem on Trees, Continuous Firefighting on Infinite Square Grids