Sequentially Swapping Colored Tokens on Graphs

• Yamanaka, Katsuhisa

• Demaine, Erik D.

• Horiyama, Takashi

• Kawamura, Akitoshi

• Nakano, Shin-ichi

• Okamoto, Yoshio

• Saitoh, Toshiki

• Suzuki, Akira

• Uehara, Ryuhei

• Uno, Takeaki

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.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/16203

Journal

• Journal of Graph Algorithms and Applications

  Journal of Graph Algorithms and Applications 23 (1), 3-27, 2019-01

  Journal of Graph Algorithms and Applications

Keywords

• reconfigration problem
• token swapping
• graph algorithm

Details

• CRID: 1050282814297957120
• NII Article ID: 120006779053
• ISSN: 15261719
• DOI: 10.7155/jgaa.00482
• Web Site: http://hdl.handle.net/10119/16203
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN