New Integrality Gap Results for the Firefighters Problem on Trees

DOI10.1007/978-3-319-51741-4_6zbMath1484.68154arXiv1601.02388OpenAlexW2237005955MaRDI QIDQ2971157

Parinya Chalermsook, Daniel Vaz

Publication date: 4 April 2017

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (2)

Asymptotic quasi-polynomial time approximation scheme for resource minimization for fire containment ⋮ The firefighter problem: further steps in understanding its complexity

Cites Work

• The firefighter problem for cubic graphs
• The firefighter problem with more than one firefighter on trees
• Approximability of the firefighter problem. Computing cuts over time
• More fires and more fighters
• Parameterized complexity of firefighting
• Fire containment in grids of dimension three and higher
• The Firefighter Problem: A Structural Analysis
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Firefighting on Trees Beyond Integrality Gaps
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New Integrality Gap Results for the Firefighters Problem on Trees