Sequentially swapping colored tokens on graphs

Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Citations (Scopus)


We consider a puzzle consisting of colored tokens on an nvertex 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 O(n3) 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, complete graphs, and cycles.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings
EditorsMd. Saidur Rahman, Hsu-Chun Yen, Sheung-Hung Poon
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319539249
Publication statusPublished - 2017
Event11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 - Hsinchu, Taiwan, Province of China
Duration: 2017 Mar 292017 Mar 31

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10167 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
Country/TerritoryTaiwan, Province of China


Dive into the research topics of 'Sequentially swapping colored tokens on graphs'. Together they form a unique fingerprint.

Cite this