**Reference**:- Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno, “Swapping Labeled Tokens on Graphs”, in
*Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014)*, Lipari Island, Italy, July 1–3, 2014, pages 364–375. **Abstract**:-
Consider a puzzle consisting of
*n*tokens on an*n*-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in*O*(*n*^{2}) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. **Availability**:- The paper is available in PostScript (2873k), gzipped PostScript (1323k), and PDF (119k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- TokenReconfiguration_TCS (Swapping Labeled Tokens on Graphs)

See also other papers by Erik Demaine.

Last updated May 5, 2021 by Erik Demaine.