| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2016-06-25 15:05 Computational Complexity of Sequential Token Swapping Problem Katsuhisa Yamanaka (Iwate Univ.), Erik D. Demaine (MIT), Takashi Horiyama (Saitama Univ.), Akitoshi Kawamura (Univ. of Tokyo), Shin-ichi Nakano (Gunma Univ.), Yoshio Okamoto (UEC), Toshiki Saitoh (Kobe Univ.), Akira Suzuki (Tohoku Univ.), Ryuhei Uehara (JAIST), Takeaki Uno (NII)  COMP2016-13 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (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) |
| (in English) | sequential token swapping problem / inapproximability / gap-preserving reduction / polynomial-time algorithms / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 116, no. 116, COMP2016-13, pp. 115-121, June 2016. | |
| Paper # | COMP2016-13 | |
| Date of Issue | 2016-06-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2016-13 |
|
| Conference Information | |
| Committee | COMP IPSJ-AL |
| Conference Date | 2016-06-24 - 2016-06-25 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2016-06-COMP-AL |
| Language | English |
| 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 |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 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) |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2016-06-25 15:05:00 |
| Presentation Time | 25 minutes |
| Registration for | COMP |
| Paper # | COMP2016-13 |
| Volume (vol) | vol.116 |
| Number (no) | no.116 |
| Page | pp.115-121 |
| #Pages | 7 |
| Date of Issue | 2016-06-17 (COMP) |
[Return to Top Page]