Sequentially Swapping Colored Tokens on Graphs

DOI10.7155/jgaa.00482zbMath1405.05116OpenAlexW2912916233MaRDI QIDQ4622769

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

Publication date: 14 February 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00482

zbMATH Keywords

puzzles on graphssequential token swapping problem

Mathematics Subject Classification ID

Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Sequentially swapping tokens: further on graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of token swapping and its variants
• The \((n^ 2-1)\)-puzzle and related relocation problems
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• An explicit lower bound for TSP with distances one and two
• Graph puzzles, homotopy, and the alternating group
• Swapping labeled tokens on graphs
• The Time Complexity of the Token Swapping Problem and Its Parallel Variants
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• Swapping Colored Tokens on Graphs
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory