Sequentially Swapping Colored Tokens on Graphs

Authors

  • Katsuhisa Yamanaka
  • Erik Demaine
  • Takashi Horiyama
  • Akitoshi Kawamura
  • Shin-ichi Nakano
  • Yoshio Okamoto
  • Toshiki Saitoh
  • Akira Suzuki
  • Ryuhei Uehara
  • Takeaki Uno

DOI:

https://doi.org/10.7155/jgaa.00482

Keywords:

sequential token swapping problem , inapproximability , gap-preserving reduction , polynomial-time algorithms

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.

Downloads

Download data is not yet available.

Downloads

Published

2019-01-01

How to Cite

Yamanaka, K., Demaine, E., Horiyama, T., Kawamura, A., Nakano, S.- ichi, Okamoto, Y., … Uno, T. (2019). Sequentially Swapping Colored Tokens on Graphs. Journal of Graph Algorithms and Applications, 23(1), 3–27. https://doi.org/10.7155/jgaa.00482