| Presentation | 2014-04-24 Swapping Labeled Tokens on Graphs Katsuhisa YAMANAKA, Erik D. DEMAINE, Takehiro ITO, Jun KAWAHARA, Masashi KIYOMI, Yoshio OKAMOTO, Toshiki SAITOH, Akira SUZUKI, Kei UCHIZAWA, Takeaki UNO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n^2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | approximation algorithm / complete bipartite graph / graph algorithm / token swapping / tree |
| Paper # | COMP2014-2 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2014/4/17(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Swapping Labeled Tokens on Graphs |
| Sub Title (in English) | |
| Keyword(1) | approximation algorithm |
| Keyword(2) | complete bipartite graph |
| Keyword(3) | graph algorithm |
| Keyword(4) | token swapping |
| Keyword(5) | tree |
| 1st Author's Name | Katsuhisa YAMANAKA |
| 1st Author's Affiliation | Iwate University() |
| 2nd Author's Name | Erik D. DEMAINE |
| 2nd Author's Affiliation | Massachusetts Institute of Technology |
| 3rd Author's Name | Takehiro ITO |
| 3rd Author's Affiliation | Tohoku University |
| 4th Author's Name | Jun KAWAHARA |
| 4th Author's Affiliation | Nara Institute of Science and Technology |
| 5th Author's Name | Masashi KIYOMI |
| 5th Author's Affiliation | Yokohama City University |
| 6th Author's Name | Yoshio OKAMOTO |
| 6th Author's Affiliation | University of Electro-Communications |
| 7th Author's Name | Toshiki SAITOH |
| 7th Author's Affiliation | Kobe University |
| 8th Author's Name | Akira SUZUKI |
| 8th Author's Affiliation | Iwate University |
| 9th Author's Name | Kei UCHIZAWA |
| 9th Author's Affiliation | Yamagata University |
| 10th Author's Name | Takeaki UNO |
| 10th Author's Affiliation | National Institute of Informatics |
| Date | 2014-04-24 |
| Paper # | COMP2014-2 |
| Volume (vol) | vol.114 |
| Number (no) | 19 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |