Winner Determination Algorithms for Graph Games with Matching Structures
Winner Determination Algorithms for Graph Games with Matching Structures
复制标题
具有匹配结构的图游戏的获胜者确定算法
DOI：
10.1007/s00453-023-01136-w
复制
发表时间：
2023
期刊：
影响因子：
1.1
通讯作者：
Kanae Yoshiwatari
中科院分区：
文献类型：
--
作者：
T. Hanaka;Hironori Kiya;Hirotaka Ono;Kanae Yoshiwatari
Cram、Domestic和Arc Kayles都是研究得很好的组合博弈。它们被解释为图上的边选择型博弈，并且在博弈期间被选择的边形成匹配。在本文中，我们定义了一个广义的游戏称为彩色弧Kayles，它包括这些游戏。彩色弧Kayles是在一个图上进行的，该图的边被着色为黑色，白色，或灰色，和黑色（分别为，白色）边缘可以仅由黑色（相应地，白色）玩家，而灰色边缘可以由黑色和白色玩家选择。我们首先观察到，彩色弧Kayles的赢家确定可以通过一个简单的算法及时完成，其中是输入图的顺序。然后，我们专注于顶点覆盖数，这是线性相关的圈数，并显示thatColored Arc Kayles，BW-Arc Kayles，和Arc Kayles分别解决的时间，，和，其中是顶点覆盖数。在此基础上，我们提出了一种基于邻域多样性的Arc Kayles算法。我们最后表明，弧Kayleson树可以及时解决，这提高了Bodlaender等人的分析的直接调整。节点Kayles的s时间算法。
Cram,Domineering, andArc Kaylesare 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 calledColored Arc Kayles, which includes these games.Colored Arc Kaylesis 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, while gray edges can be selected by both black and white players. We first observe that the winner determination forColored Arc Kaylescan be done intime by a simple algorithm, wherenis the order of the input graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show thatColored Arc Kayles,BW-Arc Kayles, andArc Kaylesare solved in time,, and, respectively, whereis the vertex cover number. Furthermore, we present an-time algorithm forArc Kayles, whereis neighborhood diversity. We finally show thatArc Kayleson trees can be solved intime, which improvesby a direct adjustment of the analysis of Bodlaender et al.’s-time algorithm forNode Kayles.