Paper by Erik D. Demaine

Reference:

Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno, “Sequentially Swapping Colored Tokens on Graphs”, in Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), Hsinchu, Taiwan, March 29–31, 2017, pages 435–447.

Abstract:

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 O(n³) 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.

Comments:

This paper is also available from SpringerLink.

Availability:

Currently unavailable. If you are in a rush for copies, contact me.

[Google Scholar search]

Related papers:

SequentialTokenSwapping_JGAA (Sequentially Swapping Colored Tokens on Graphs)