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 · Journal of Graph Algorithms and Applications · 2019
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.