| dc.contributor |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
|
| dc.contributor |
Demaine, Erik D. |
|
| dc.creator |
Yamanaka, Katsuhisa |
|
| dc.creator |
Demaine, Erik D. |
|
| dc.creator |
Ito, Takehiro |
|
| dc.creator |
Kawahara, Jun |
|
| dc.creator |
Kiyomi, Masashi |
|
| dc.creator |
Okamoto, Yoshio |
|
| dc.creator |
Saitoh, Toshiki |
|
| dc.creator |
Suzuki, Akira |
|
| dc.creator |
Uchizawa, Kei |
|
| dc.creator |
Uno, Takeaki |
|
| dc.date |
2015-11-23T14:41:38Z |
|
| dc.date |
2015-11-23T14:41:38Z |
|
| dc.date |
2014 |
|
| dc.date.accessioned |
2023-03-01T18:12:01Z |
|
| dc.date.available |
2023-03-01T18:12:01Z |
|
| dc.identifier |
978-3-319-07889-2 |
|
| dc.identifier |
978-3-319-07890-8 |
|
| dc.identifier |
0302-9743 |
|
| dc.identifier |
1611-3349 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/99984 |
|
| dc.identifier |
Yamanaka, Katsuhisa, 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.” Fun with Algorithms (2014): 364–375. |
|
| dc.identifier |
https://orcid.org/0000-0003-3803-5703 |
|
| dc.identifier.uri |
http://localhost:8080/xmlui/handle/CUHPOERS/279128 |
|
| dc.description |
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 [superscript 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. |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 24.3660) |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 24106010) |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 24700130) |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 25106502) |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 25106504) |
|
| dc.description |
Japan. Ministry of Education, Culture, Sports, Science and Technology (Japan Society for the Promotion of Science ELC Project Grant 25330003) |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.publisher |
Springer-Verlag |
|
| dc.relation |
http://dx.doi.org/10.1007/978-3-319-07890-8_31 |
|
| dc.relation |
Fun with Algorithms |
|
| dc.rights |
Creative Commons Attribution-Noncommercial-Share Alike |
|
| dc.rights |
http://creativecommons.org/licenses/by-nc-sa/4.0/ |
|
| dc.source |
MIT web domain |
|
| dc.title |
Swapping Labeled Tokens on Graphs |
|
| dc.type |
Article |
|
| dc.type |
http://purl.org/eprint/type/ConferencePaper |
|