强罗马控制问题的算法与应用研究文献综述

1. 文献综述（或调研报告）：

Ian Stewart在1999年12月的Scientific American上发文对罗马控制问题进行了描述，但由于文章科普的性质，其中并未涉及复杂的数学表达。Stewart在文章中提及了ReVell和Rosing（2000）的研究成果，并给出了简单的解决方案。ReVell和Rosing（2000）则正式将罗马控制问题引入了学术界，并从集合覆盖（Set Covering）和最大覆盖（Maximal Covering）的角度建立了罗马控制问题的数学模型，其中最大覆盖模型的罗马控制问题可以看作集合覆盖模型罗马控制问题的一个衍生问题。ReVell和Rosing给出了罗马控制问题的解并且解决了19世纪不列颠帝国和冷战后美国的全球军队部署策略问题。在此后，几乎没有文章从数学规划角度对罗马控制问题进行研究，直到Ivanović（2016）通过松弛方法改进ReVelle和Rosing的模型。

Cockayne等（2004）将罗马控制问题引入了图论的研究中。他们给出了罗马控制问题的数学定义，包括罗马控制函数与罗马控制数，并重点研究了罗马控制数的性质。Henning和Hedetniemi重点研究了弱罗马控制问题在特殊的图，如环、路径和森林等中的性质。Rubalcaba和Slater（2007）引入了罗马控制影响因子的概念，用以评估罗马控制数的效率。Fu等（2009）研究了罗马控制问题在正则图中的性质。Chanbers等（2009）优化了之前罗马控制数的上下界，取得了更好的结果。Sheikholeslami和Volkmann（2010）将一张图中罗马控制函数的最大数量称为罗马控制划分数并研究了相关性质。Tan等（2016）经一步考虑了罗马控制划分数的计算问题，证明了计算罗马控制划分数是NP-Hard问题，并给出了其近似值。Targhi等（2011）定义了罗马控制独特响应数并给出了其性质以及边界。Liu和Chang（2012）在图的最小度为3的条件下给出了罗马控制数更优的上界。Chellali等（2005）比较了罗马控制数与完全控制数（Total Domination Number）之间的关系。Chellali（2016）从罗马独立数等的定义衍生出罗马控制链的定义，并给出了其性质与上下界。Alvarado等（2016）在树的范畴内给出了罗马控制和弱罗马控制之间的等式关系。Chellali等（2016）则考虑了罗马控制数和独立罗马控制数下界之间的关系。Samovivkin（2016）将删去任意一节点后，罗马控制数不变的图归入类。

同时，罗马控制问题的许多延伸问题也受到了广泛关注。Henning和Hedetniemi（2003）定义了弱罗马控制问题（Weak Roman Domination Problem），弱罗马控制数和弱罗马控制函数，作为一种新的策略防御罗马帝国。Henning（2003）假设罗马帝国面临多次连续（不同时）的进攻，将问题定义为k-罗马控制问题，同时对k-罗马控制数的性质及问题的复杂度做了深入讨论。Kammerling和Volkmann（2009）定义了罗马k-控制问题，要求每一个没有驻军的节点必须与之少个驻军的节点相邻。Hansberg和Volkmann（2009）则在一篇文章中同时给出了罗马k-控制问题与k-罗马控制问题更优的上界。Aram等（2013）［x］考虑了k-距离罗马控制问题，即在每个驻军数为0节点的k距离内，必须有一个驻军数为2的节点存在。Ahangar等（2015）、Volkmann（2015）、Henning和Volkmann（2015）、Henning和Volkmann（2016）、Volkmann（2016）和Shao（2017）均将符号控制问题引入了罗马控制问题，分别从不同的角度研究了罗马符号控制问题及延伸问题。Beeler等（2016）考虑了双重罗马控制问题，要求每个驻军数量为0的节点周围必须有两个驻军数为2的节点或一个驻军数为1和一个驻军数为3的节点。Ahangar等（2017）则继续了双重罗马控制问题的研究，给出了更优的边界值。Pushpam和Padmapriea（2016）定义了罗马全局控制，即前述条件必须满足一个图和它的补图。Ahangar等（2016）研究了罗马全控制问题。Amjadi等（2017）则在二者基础上加以整合，考虑了罗马全局全控制问题。Ahangar（2016）继续了罗马全局控制问题的研究，给出了图的罗马控制数和图的控制数之间的关系及条件。Ahangar等（2016）和Ahangar等（2017）考虑了最大罗马控制问题的性质并证明了其属于NP-Complete问题。Chellali等（2016）定义了罗马{2}-控制问题，即每一个驻军数量为0的节点必须与两个驻军数量为1的节点相邻或与一个驻军数量为2的节点相邻。Rahmouni和Chellali（2016）则在此基础上研究了独立罗马{2}-控制问题。其他的延伸问题有，Ahangar等（2017）研究了混合罗马控制问题；Henning等（2017）研究了完美罗马控制问题在树中的性质；Bahremandpour等（2017）将博弈论引入罗马控制问题，定义了罗马博弈控制问题并给出了相关性质。Aacute;lvarez-Ruiz等（2017）定义了强罗马控制问题，即图可能受到同时多次的进攻，每一个驻军的节点需要防御其至少一半未驻军的邻居节点。

现有研究大多集中于罗马控制问题及其延伸问题的性质，而关于其算法的研究并不多。ReVelle和Rosing（2000）在最初提出罗马控制问题时给出了求解的算法。他们从集合覆盖问题（Set Covering Problem）和最大覆盖问题（Maximal Covering Problem）的角度提出了两套0-1整数规划算法，求解了最初的罗马控制问题。Ivanović（2016）通过特定的松弛方法改进了ReVelle和Rosing的模型。Liedloff等（2008）证明了罗马控制问题在一些图上可于线性时间内求解，并给出了相应的算法。Chapelle等（2017）给出了弱罗马控制问题的确切算法以及弱罗马控制问题在区间图上的线性时间算法。Álvarez-Ruiz等（2017）证明了强罗马控制问题属于NP-Complete问题。