论文标题
一般职位回避游戏和一般职位游戏的硬度
The general position avoidance game and hardness of general position games
论文作者
论文摘要
给定图形$ g $，如果$ g $中的$ s $ s $顶点是一般位置集，如果$ s $中的三重顶点躺在$ g $中的最短路径上。一般位置成就/避免游戏是在图表$ g $上进行的，玩家A和B会选择$ g $的顶点。如果以前没有选择过顶点，则通过玩家选择顶点是法律举动，而到目前为止，选定的顶点集构成了$ g $的一般位置集。选择最后一个顶点的玩家是一般职位成就游戏中的赢家，并且是回避游戏的失败者。在本文中，我们证明，即使在直径为4的图表上，一般位置成就/避免游戏也是Pspace complete。为此，我们证明了经典节点kayles游戏的\ textit {misère}玩游戏也是pspace-complete。作为积极的结果，我们获得了线性时间算法，以决定具有完整第二个因素的Rook的图，网格，圆柱和词典产品中的一般位置回避游戏的获胜者。
Given a graph $G$, a set $S$ of vertices in $G$ is a general position set if no triple of vertices from $S$ lie on a common shortest path in $G$. The general position achievement/avoidance game is played on a graph $G$ by players A and B who alternately select vertices of $G$. A selection of a vertex by a player is a legal move if it has not been selected before and the set of selected vertices so far forms a general position set of $G$. The player who picks the last vertex is the winner in the general position achievement game and is the loser in the avoidance game. In this paper, we prove that the general position achievement/avoidance games are PSPACE-complete even on graphs with diameter at most 4. For this, we prove that the \textit{misère} play of the classical Node Kayles game is also PSPACE-complete. As positive results, we obtain linear time algorithms to decide the winning player of the general position avoidance game in rook's graphs, grids, cylinders, and lexicographic products with complete second factors.
