Sequentially Swapping Tokens: Further on Graph Classes
Sequentially Swapping Tokens: Further on Graph Classes
复制标题
顺序交换令牌：进一步了解图类
DOI：
10.1007/978-3-031-23101-8_15
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Otachi Yota
中科院分区：
文献类型：
--
作者：
Kiya Hironori;Okada Yuto;Ono Hirotaka;Otachi Yota
我们研究了15难题的以下变体。给定一个图和顶点上的两个标记放置，我们希望找到一个最小长度的行走（如果存在），使得沿着行走的标记交换序列沿着从另一个给定的标记放置中获得一个。这个问题由Yamanaka等人引入作为顺序令牌交换。[JGAA 2019]，他们表明这个问题一般来说是棘手的，但对于树，完全图和循环来说是多项式时间可解的。在本文中，我们提出了一个多项式时间算法的块仙人掌图，其中包括所有以前已知的情况。我们还提出了一般的工具，显示限制图类，如弦图和弦二分图的问题的硬度。我们还表明，这个问题是很难的网格和国王的图，这是对应于15难题和它的变体与放松移动的图形。
We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the sequence of token swappings along the walk obtains one of the given token placements from the other one. This problem was introduced asSequential Token Swappingby Yamanaka et al. [JGAA 2019], who showed that the problem is intractable in general but polynomial-time solvable for trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for block-cactus graphs, which include all previously known cases. We also present general tools for showing the hardness of problem on restricted graph classes such as chordal graphs and chordal bipartite graphs. We also show that the problem is hard on grids and king’s graphs, which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.
登录
查看更多内容
在图上顺序交换彩色标记
影响因子：
--
作者：
Katsuhisa Yamanaka;Erik D. Demaine;Takashi Horiyama;Akitoshi Kawamura;Shin-Ichi Nakano;Yoshio Okamoto;Toshiki Saitoh;Akira Suzuki;Ryuhei Uehara;and Takeaki Uno
通讯作者：
and Takeaki Uno
影响因子：
2.3
作者：
Nishimura, Naomi
通讯作者：
Nishimura, Naomi
影响因子：
1.6
作者：
Fomin, Fedor V.;Golovach, Petr A.;Saurabh, Saket
通讯作者：
Saurabh, Saket
(n 2-1)-谜题及相关的搬迁问题
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
D. A N I E L R A T N E R A N D M A N F R E D W A R M
通讯作者：
D. A N I E L R A T N E R A N D M A N F R E D W A R M
$(n^2-1)$-难题很难的简单证明
DOI：
10.1016/j.tcs.2018.04.031
发表时间：
2017
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
E. Demaine;Mikhail Rudoy
通讯作者：
Mikhail Rudoy