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

DOI10.1007/978-3-540-92182-0_25zbMath1183.05077OpenAlexW1530136340MaRDI 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

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (22)

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

This page was built for publication: Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm