Scholarlink

<p>In the classical firefighter game, a fire breaks out on some vertices of an undirected connected graph at time zero. At each subsequent time step, a fixed number of firefighters can protect one vertex each from catching fire. Afterwards, the fire spreads from each burning vertex to every adjacent vertex that is neither burning nor defended. The game ends when the fire can no longer spread. The goal is to find a defense strategy that maximizes the number of non-burning (saved) vertices. In this work, we first revisit the classical integer linear programming formulation and then present several improvements for it, as well as two new formulations and tighter bounds on the maximum duration of the game. Moreover, we relax the classical assumptions that all vertices have uniform values and costs, i.e., we allow vertices to have different values and costs for being defended. Furthermore, instead of a fixed number of firefighters, we are given a defense budget that we can spend each time step to defend the vertices. We call this the cost-value firefighter game. We present three different integer linear programming formulations for the problem, along with a series of inequalities to strengthen the formulations and tight bounds on the maximum duration of the game.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Advancing firefighter games: novel integer programming formulations and the cost-value model

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月17日

查看全文
  • Marta Baldomero-Naranjo,
  • Jörg Kalcsics,
  • Antonio M. Rodríguez-Chía,
  • Catriona Wedderburn

摘要

In the classical firefighter game, a fire breaks out on some vertices of an undirected connected graph at time zero. At each subsequent time step, a fixed number of firefighters can protect one vertex each from catching fire. Afterwards, the fire spreads from each burning vertex to every adjacent vertex that is neither burning nor defended. The game ends when the fire can no longer spread. The goal is to find a defense strategy that maximizes the number of non-burning (saved) vertices. In this work, we first revisit the classical integer linear programming formulation and then present several improvements for it, as well as two new formulations and tighter bounds on the maximum duration of the game. Moreover, we relax the classical assumptions that all vertices have uniform values and costs, i.e., we allow vertices to have different values and costs for being defended. Furthermore, instead of a fixed number of firefighters, we are given a defense budget that we can spend each time step to defend the vertices. We call this the cost-value firefighter game. We present three different integer linear programming formulations for the problem, along with a series of inequalities to strengthen the formulations and tight bounds on the maximum duration of the game.