More fires and more fighters

DOI10.1016/J.DAM.2013.04.008MaRDI QIDQ2444533zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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
• Asymptotic surviving rate of trees with multiple fire sources
• Firefighting as a strategic game
• 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)