论文标题
具有匹配结构的图形游戏的获胜者确定算法
Winner Determination Algorithms for Graph Games with Matching Structures
论文作者
论文摘要
Cram，霸气和凯尔斯（Arc Kayles）是研究精彩的组合游戏。它们被解释为图形上的边缘选择型游戏，并且在游戏中选定的边缘形成了匹配。在本文中，我们定义了一个名为Colored Arc Kayles的广义游戏，其中包括这些游戏。彩色弧凯尔斯（Kayles）在图表上播放，其边缘以黑色，白色或灰色和黑色（分别，白色）边缘颜色，只能由黑色（分别，白色）播放器选择，尽管灰色边缘可以由黑白玩家选择。我们首先观察到，可以通过简单的算法以$ o^*（2^n）$时间在$ o^*（2^n）$时间以$ o^*（2^n）$的确定，其中$ n $是图的顺序。然后，我们专注于顶点封面编号，该封面与转弯数是线性相关的，并表明彩色弧kayles，bw-arc kayles和arc kayles在时间$ o^*（1.4143^{τ^2+3.17τ}）的时间内解决了。 $ o^*（1.1893^{τ^2+6.34τ}）$，其中$τ$是顶点封面号。此外，我们提出了一个$ o^*（（（n/ν+1）^ν）$ - Arc Kayles的时间算法，其中$ν$是邻居的多样性。 We finally show that Arc Kayles on trees can be solved in $O^* (2^{n/2})(=O(1.4143^n))$ time, which improves $O^*(3^{n/3})(=O(1.4423^n))$ by a direct adjustment of the analysis of Bodlaender et al.'s $O^*(3^{n/3})$-time节点kayles的算法。
Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in $O^*(2^n)$ time by a simple algorithm, where $n$ is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time $O^*(1.4143^{τ^2+3.17τ})$, $O^*(1.3161^{τ^2+4τ})$, and $O^*(1.1893^{τ^2+6.34τ})$, respectively, where $τ$ is the vertex cover number. Furthermore, we present an $O^*((n/ν+1)^ν)$-time algorithm for Arc Kayles, where $ν$ is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in $O^* (2^{n/2})(=O(1.4143^n))$ time, which improves $O^*(3^{n/3})(=O(1.4423^n))$ by a direct adjustment of the analysis of Bodlaender et al.'s $O^*(3^{n/3})$-time algorithm for Node Kayles.
