| Presentation | 2016-06-25 Computational Complexity of Sequential Token Swapping Problem Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider a puzzle consisting of colored tokens on an $n$-vertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to ``sequentially'' move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen-Puzzle and is solvable in n^3 token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees and complete graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | sequential token swapping problem / inapproximability / gap-preserving reduction / polynomial-time algorithms |
| Paper # | COMP2016-13 |
| Date of Issue | 2016-06-17 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2016/6/24(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) / Ryuhei Uehara(北陸先端大) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) / (Kobe Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computational Complexity of Sequential Token Swapping Problem |
| Sub Title (in English) | |
| Keyword(1) | sequential token swapping problem |
| Keyword(2) | inapproximability |
| Keyword(3) | gap-preserving reduction |
| Keyword(4) | polynomial-time algorithms |
| 1st Author's Name | Katsuhisa Yamanaka |
| 1st Author's Affiliation | Iwate University(Iwate Univ.) |
| 2nd Author's Name | Erik D. Demaine |
| 2nd Author's Affiliation | Massachusetts Institute of Technology(MIT) |
| 3rd Author's Name | Takashi Horiyama |
| 3rd Author's Affiliation | Saitama University(Saitama Univ.) |
| 4th Author's Name | Akitoshi Kawamura |
| 4th Author's Affiliation | The University of Tokyo(Univ. of Tokyo) |
| 5th Author's Name | Shin-ichi Nakano |
| 5th Author's Affiliation | Gunma University(Gunma Univ.) |
| 6th Author's Name | Yoshio Okamoto |
| 6th Author's Affiliation | The University of Electro-communications(UEC) |
| 7th Author's Name | Toshiki Saitoh |
| 7th Author's Affiliation | Kobe University(Kobe Univ.) |
| 8th Author's Name | Akira Suzuki |
| 8th Author's Affiliation | Tohoku University(Tohoku Univ.) |
| 9th Author's Name | Ryuhei Uehara |
| 9th Author's Affiliation | Japan Advanced Institute of Science and Technology(JAIST) |
| 10th Author's Name | Takeaki Uno |
| 10th Author's Affiliation | National Institute of Informatics(NII) |
| Date | 2016-06-25 |
| Paper # | COMP2016-13 |
| Volume (vol) | vol.116 |
| Number (no) | COMP-116 |
| Page | pp.pp.115-121(COMP), |
| #Pages | 7 |
| Date of Issue | 2016-06-17 (COMP) |