Spanning Trees and the Complexity of Flood-Filling Games
Spanning Trees and the Complexity of Flood-Filling Games
复制标题
生成树和洪水填充游戏的复杂性
DOI：
--
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
Alexander Scott
中科院分区：
文献类型：
--
作者：
Kitty Meeks;Alexander Scott
我们考虑与组合游戏（自由式）洪水有关的问题，其中玩家的目标是使彩色图单色，并以最小的洪水操作数量。我们表明，淹没任何给定的图G所需的最小移动次数等于最小值，在g的所有跨树T中，泛滥t的移动次数。洪水填充问题的时间算法。首先，我们可以在多项式时间内计算只有多项式连接子图的图形所需的最小移动数。其次，如果有任何有色连接的图形和有界大小的顶点的子集，则可以在多项式时间内计算连接该子集所需的移动数。
We consider problems related to the combinatorial game (Free-) Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.
洪水填充游戏的复杂性
影响因子：
0.5
作者：
Clifford R
通讯作者：
Clifford R