Sequentially Swapping Tokens: Further on Graph Classes

Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

抄録

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 as Sequential Token Swapping by 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.

本文言語英語
ホスト出版物のタイトルSOFSEM 2023
ホスト出版物のサブタイトルTheory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings
編集者Leszek Gasieniec
出版社Springer Science and Business Media Deutschland GmbH
ページ222-235
ページ数14
ISBN(印刷版)9783031231001
DOI
出版ステータス出版済み - 2023
イベント48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023 - Nový Smokovec, スロバキア
継続期間: 1月 15 20231月 18 2023

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
13878 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023
国/地域スロバキア
CityNový Smokovec
Period1/15/231/18/23

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般

フィンガープリント

「Sequentially Swapping Tokens: Further on Graph Classes」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル