Kayles and Nimbers
Kayles and Nimbers
复制标题
凯尔斯和尼伯斯
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Kratsch
中科院分区：
文献类型：
--
作者：
H. Bodlaender;D. Kratsch
Kayles是一个关于图的组合游戏。两个玩家交替地从一个给定的图G中选择一个顶点--选择的顶点不能与已经选择的顶点相邻或相等。最后一个能选择顶点的玩家赢了这场游戏。确定哪一个玩家有获胜策略的问题是已知的PSPACE-Complete。由于凯尔斯博弈的某些特点，可以用斯普拉格？格朗迪理论进行分析。这样，我们就可以证明该问题在有界小行星数的图上是多项式时间可解的。证明了该问题在共可比图和圆弧图上的时间为O(N3)，在余图上的时间为O(n1+1/log3)=O(n1.631)。
Kayles is a combinatorial game on graphs. Two players select alternatingly a vertex from a given graph G?a chosen vertex may not be adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. The problem to determine which player has a winning strategy is known to be PSPACE-complete. Because of certain characteristics of the Kayles game, it can be analyzed with Sprague?Grundy theory. In this way, we can show that the problem is polynomial time solvable on graphs with a bounded asteroidal number. It is shown that the problem can be solved in O(n3) time on cocomparability graphs and circular arc graphs, and in O(n1+1/log3)=O(n1.631) time on cographs.