论文标题
消防员问题与最低预算：单位磁盘图的硬度和近似算法
Firefighter Problem with Minimum Budget: Hardness and Approximation Algorithm for Unit Disk Graphs
论文作者
论文摘要
单位磁盘图是代表磁盘图和间隔图的相交的一组图。这些图非常重要，因为它们与无线通信网络的结构相似性。单位磁盘图上的消防员问题很有趣，因为它模拟了在无线网络中扩散的病毒，并要求解决方案以阻止它。在本文中，我们考虑了最小预算的消防员问题，该问题的目标是确定所需的最小消防员数量，以及在每次瞬间放置它们的节点，以节省给定图形的给定顶点和防火节点。我们表明，单位磁盘图中的最小预算消防员问题是NP-HARD。我们还提出了恒定因子近似算法。
Unit disk graphs are the set of graphs which represent the intersection of disk graphs and interval graphs. These graphs are of great importance due to their structural similarity with wireless communication networks. Firefighter problem on unit disk graph is interesting as it models the virus spreading in an wireless network and asks for a solution to stop it. In this paper, we consider the MIN-BUDGET firefighter problem where the goal is to determine the minimum number of firefighters required and the nodes to place them at each time instant to save a given set of vertices of a given graph and a fire breakout node. We show that, the MIN-BUDGET firefighter problem in a unit disk graph is NP-Hard. We also present a constant factor approximation algorithm.
