The firefighter problem: empirical results on random graphs

DOI10.1016/J.COR.2015.02.004zbMath1348.05190OpenAlexW1984407874MaRDI QIDQ337557

Carlos García-Martínez, Manuel Lozano, Francisco J. Rodriguez, Christian Blum

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2015.02.004

zbMATH Keywords

heuristicsfirefighter probleminteger linear programming techniques

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (5)

Finding exact solutions for the geometric firefighter problem in practice ⋮ A matheuristic for the firefighter problem on graphs ⋮ The maximum clique interdiction problem ⋮ Estimation of Distribution Algorithms for the Firefighter Problem ⋮ Solving the geometric firefighter routing problem via integer programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fighting constrained fires in graphs
• Firefighting on square, hexagonal, and triangular grids
• The surviving rate of an outerplanar graph for the firefighter problem
• The surviving rate of an infected network
• The 2-surviving rate of planar graphs without 4-cycles
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• The surviving rate of planar graphs
• The firefighter problem for cubic graphs
• A study on the use of non-parametric tests for analyzing the evolutionary algorithms' behaviour: a case study on the CEC'2005 special session on real parameter optimization
• Geometric algorithms and combinatorial optimization
• 3/2 firefighters are not enough
• The firefighter problem with more than one firefighter on trees
• A lower bound of the surviving rate of a planar graph with girth at least seven
• Multi-start methods for combinatorial optimization
• The firefighter problem for graphs of maximum degree three
• Approximability of the firefighter problem. Computing cuts over time
• More fires and more fighters
• Fire containment in grids of dimension three and higher
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Parameterized Complexity of Firefighting Revisited
• Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem
• The Surviving Rate of a Graph for the Firefighter Problem
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity
• Approximations of the critical region of the fbietkan statistic
• Fire Containment in Planar Graphs

This page was built for publication: The firefighter problem: empirical results on random graphs