Paper by Erik D. Demaine
- 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.
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(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.
- This paper is also available from SpringerLink.
- Currently unavailable. If you are in a rush for copies,
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 22, 2018 by