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 -