Fighting constrained fires in graphs

DOI10.1016/J.TCS.2012.01.041MaRDI QIDQ428868zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, Margaret-Ellen Messinger, Paweł Prałat

Publication date 25 June 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.01.041

zbMATH Keywords

surviving raterandom regular graphsfirefighterinfinite random graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Surviving rate of graphs and firefighter problem
• Surviving rate of graphs and firefighter problem
• Sparse graphs are not flammable
• The surviving rate of a graph for the firefighter problem
• Surviving rates of graphs with bounded treewidth for the firefighter problem

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Asymmetric graphs
• Expander graphs and their applications
• Explicit construction of linear sized tolerant networks
• Fire containment in grids of dimension three and higher
• Firefighting on trees: How bad is the greedy algorithm?
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• On a pursuit game on Cayley graphs
• Sparse graphs are not flammable
• Surviving rates of graphs with bounded treewidth for the firefighter problem
• The Firefighter problem: a survey of results, directions and questions
• The cop density of a graph
• The firefighter problem for cubic graphs
• The surviving rate of a graph for the firefighter problem
• The surviving rate of an infected network
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(11)

• Surviving rate of graphs and firefighter problem
• Firefighting on trees
• Firefighting on a random geometric graph
• Surviving rate of graphs and firefighter problem
• Firefighting on trees and Cayley graphs
• scientific article; zbMATH DE number 5016646 (Why is no real title available?)
• Sparse graphs are not flammable
• The spread of fire on a random multigraph
• Firefighting as a strategic game
• The firefighter problem: empirical results on random graphs
• Fire Containment in Planar Graphs

This page was built for publication: Fighting constrained fires in graphs

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