|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/15101
|
| タイトル: | Shortest Reconfiguration of Sliding Tokens on a Caterpillar |
| 著者: | Yamada, Takeshi
Uehara, Ryuhei |
| キーワード: | independent set
reconfiguration problem
sliding token
catarpillar |
| 発行日: | 2016-03-29 |
| 出版者: | Springer |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 9627 |
| 開始ページ: | 236 |
| 終了ページ: | 248 |
| DOI: | 10.1007/978-3-319-30139-6_19 |
| 抄録: | For given two independent sets I_b and I_r of a graph, the sliding token problem is to determine if there exists a sequence of independent sets which transforms I_b into I_r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. These problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems for finding a shortest reconfiguration sequence are investigated. For the 3SAT reconfiguration problem, a trichotomy for the complexity of finding the shortest sequence has been shown; it is in P, NP-complete, or PSPACE-complete in certain conditions. Even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. We show nontrivial polynomial time algorithms for finding a shortest sequence between two independent sets for some graph classes. As far as the authors know, one of them is the first polynomial time algorithm for the shortest sliding token problem that requires detours of tokens. |
| Rights: | This is the author-created version of Springer, Takeshi Yamada and Ryuhei Uehara, Lecture Notes in Computer Science, 9627, 2016, 236-248. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-319-30139-6_19 |
| URI: | http://hdl.handle.net/10119/15101 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 23595.pdf | | 406Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
