A Survey on the Complexity of Flood-Filling Games
A Survey on the Complexity of Flood-Filling Games
复制标题
关于洪水填充游戏复杂性的调查
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
U. Souza
中科院分区：
文献类型：
--
作者：
M. Fellows;Frances A. Rosamond;M. Silva;U. Souza
这项调查是为了纪念科学和教育先驱Juraj Hromkovic教授的生日庆祝活动。在这项调查中，我们回顾了最近的结果，一个球员的洪水填充游戏的图形，洪水，它和自由洪水，它，其中的球员的目标是使董事会单色与最少数量的洪水移动。对于许多着色图问题，洪水填充博弈在生物信息学中有相关的解释。Flood-It和Free-Flood-It的原始版本在（n）上播放 imes m）网格，但有几项研究致力于分析这些游戏的复杂性时，“板”（图）属于其他图形类。一个完整的映射的洪水填充游戏的复杂性树，绘制单一和聚合参数化的后果。树上的泛洪问题和限制最短公共超序列（RSCS）问题是类似的。洪水-它仍然是NP难时，3色树。一个通用的框架，减少从洪水，它到自由洪水，它被重新审视。这些游戏的复杂性行为进行调查时，在各种图，如笛卡尔产品的循环和路径，圆形网格，分裂图，可比较图，和AT-自由图。我们回顾了最近的调查参数化的复杂性的洪水，它的最小顶点覆盖的大小是结构参数。游戏的一些教育方面也进行了审查。祝你生日快乐！
This survey is offered in honour of the special occasion of the birthday celebration of science and education pioneer Professor Juraj Hromkovic. In this survey, we review recent results on one-player flood-filling games on graphs, Flood-It and Free-Flood-It, in which the player aims to make the board monochromatic with a minimum number of flooding moves. As for many colored graph problems, flood-filling games have relevant interpretations in bioinformatics. The original versions of Flood-It and Free-Flood-It are played on (n imes m) grids, but several studies were devoted to analyzing the complexity of these games when the “board” (the graph) belongs to other graph classes. A complete mapping of the complexity of flood-filling games on trees is presented, charting the consequences of single and aggregate parameterizations. The Flood-It problem on trees and the Restricted Shortest Common Supersequence (RSCS) problem are analogous. Flood-It remains NP-hard when played on 3-colored trees. A general framework for reducibility from Flood-It to Free-Flood-It is revisited. The complexity behavior of these games when played on various kinds of graphs is surveyed, such as Cartesian products of cycles and paths, circular grids, split graphs, co-comparability graphs, and AT-free graphs. We review a recent investigation of the parameterized complexity of Flood-It when the size of a minimum vertex cover is the structural parameter. Some educational aspects of the game are also reviewed. Happy Birthday, Juraj!
洪水填充游戏的复杂性
影响因子：
0.5
作者：
Clifford R
通讯作者：
Clifford R