Slash and burn on graphs — Firefighting with general weights

详细信息    查看全文

• 作者：Vitor Costa^a ; ^{vitorsilcost@mat.uff.br" class="auth_mail" title="E-mail the corresponding author} ; Simone Dantas^a ; ^{sdantas@im.uff.br" class="auth_mail" title="E-mail the corresponding author} ; Mitre C. Dourado^b ; ^{mitre@dcc.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Lucia Penso^c ; ^{lucia.penso@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^c ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Firefighter game ; Surviving rate
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 September 2016
• 年：2016
• 卷：210
• 期：Complete
• 页码：4-13
• 全文大小：431 K

文摘

In Hartnell’s firefighter game a player tries to contain a fire breaking out at some vertex of a graph and spreading in rounds from burned vertices to their neighbors, by defending one vertex in each round, which will remain protected from the fire throughout the rest of the game. The objective of the player is to save as many vertices as possible from burning.

Here we study a generalization for weighted graphs, where the weights can be positive as well as negative. The objective of the player is to maximize the total weight of the saved vertices of positive weight minus the total weight of the burned vertices of negative weight, that is, the player should save vertices of positive weight and let vertices of negative weight burn. We prove that this maximization problem is already hard for binary trees and describe two greedy approximation algorithms for trees. Furthermore, we discuss a weighted version of the surviving rate.