TY - GEN
T1 - Swapping labeled tokens on graphs
AU - Yamanaka, Katsuhisa
AU - Demaine, Erik D.
AU - Ito, Takehiro
AU - Kawahara, Jun
AU - Kiyomi, Masashi
AU - Okamoto, Yoshio
AU - Saitoh, Toshiki
AU - Suzuki, Akira
AU - Uchizawa, Kei
AU - Uno, Takeaki
N1 - Funding Information:
We are grateful to Takashi Horiyama, Shin-ichi Nakano and Ryuhei Uehara for their comments on related work and fruitful discussions with them. This work is supported in part by NSF grant CCF-1161626 and DARPA/AFOSR grant FA9550-12-1-0423 , and by MEXT/JSPS KAKENHI , including the ELC project, Grant Numbers 24106010 , 24700130 , 25106502 , 25106504 , 25330003 , 26730001 .
PY - 2014
Y1 - 2014
N2 - 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(n2) 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.
AB - 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(n2) 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.
UR - http://www.scopus.com/inward/record.url?scp=84903698259&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84903698259&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-07890-8_31
DO - 10.1007/978-3-319-07890-8_31
M3 - Conference contribution
AN - SCOPUS:84903698259
SN - 9783319078892
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 364
EP - 375
BT - Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings
PB - Springer Verlag
T2 - 7th International Conference on Fun with Algorithms, FUN 2014
Y2 - 1 July 2014 through 3 July 2014
ER -