Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
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, and Takeaki Uno
Vol. 23, no. 1, pp. 3-27, 2019. Regular paper.
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.
Submitted: September 2017.
Reviewed: May 2018.
Revised: June 2018.
Reviewed: October 2018.
Revised: October 2018.
Accepted: October 2018.
Final: November 2018.
Published: January 2019.