More fires and more fighters

DOI10.1016/J.DAM.2013.04.008zbMATH Open1285.05121OpenAlexW2095274987MaRDI QIDQ2444533FDOQ2444533

Authors: Vítor Costa, Simone Dantas, Mitre C. Dourado, Dieter Rautenbach, Lucia Draque Penso 

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.04.008

Recommendations

• Firefighting on trees
• Surviving rate of graphs and firefighter problem
• Firefighting as a strategic game
• Asymptotic surviving rate of trees with multiple fire sources
• Firefighting as a game

zbMATH Keywords

surviving ratefirefighter game

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Network design and communication in computer systems (68M10)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The firefighter problem with more than one firefighter on trees
• The firefighter problem for graphs of maximum degree three
• Surviving rates of graphs with bounded treewidth for the firefighter problem
• The surviving rate of a graph for the firefighter problem
• The Firefighter problem: a survey of results, directions and questions
• Firefighting on trees: How bad is the greedy algorithm?
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Title not available (Why is that?)
• Fire containment in grids of dimension three and higher

Cited In (16)

• Surviving rate of graphs and firefighter problem
• Firefighting as a game
• The 2-surviving rate of planar graphs without 5-cycles
• Solving the geometric firefighter routing problem via integer programming
• Planar graphs without chordal 5-cycles are 2-good
• Finding exact solutions for the geometric firefighter problem in practice
• New integrality gap results for the firefighters problem on trees
• Slash and burn on graphs -- firefighting with general weights
• Firefighting as a strategic game
• Asymptotic surviving rate of trees with multiple fire sources
• Online firefighting on trees
• Estimation of distribution algorithms for the firefighter problem
• The Firefighter Problem: A Structural Analysis
• The firefighter problem: empirical results on random graphs
• The burning of the snark
• The firefighter problem: further steps in understanding its complexity

This page was built for publication: More fires and more fighters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444533)