Distance-restricted firefighting on finite graphs

DOI10.1016/J.TCS.2025.115658MaRDI QIDQ6884849zbMATH OpenFDO

Authors Andrea Burgess, John A. Hawkin, Alexander Howse, John Marcoux, David A. Pike

Publication date 12 December 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115658

zbMATH Keywords

finite graphsfirefightinggames on graphsNP-completeness

Mathematics Subject Classification ID

Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Cites work

• A note on two problems in connexion with graphs
• Computational Complexity
• Continuous firefighting on infinite square grids
• Fire containment in grids of dimension three and higher
• scientific article; zbMATH DE number 5016646 (Why is no real title available?)
• scientific article; zbMATH DE number 1506515 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Parallelizing the dual revised simplex method
• Paths, Trees, and Flowers
• Reducibility among combinatorial problems
• The firebreak problem
• The firefighter problem for graphs of maximum degree three
• The firefighter problem with more than one firefighter on trees
• The Firefighter problem: a survey of results, directions and questions
• The surviving rate of a graph for the firefighter problem
• Undirected connectivity in log-space

This page was built for publication: Distance-restricted firefighting on finite graphs

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