Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2015.01.052 | Theoretical Computer Science |
Keywords | Field | DocType |
Approximation,Complete bipartite graph,Graph algorithm,Sorting network,Tree | Graph,Swap (computer programming),Discrete mathematics,Combinatorics,Vertex (geometry),Computer science,Bipartite graph,Time complexity,Security token | Conference |
Volume | Issue | ISSN |
586 | C | 0304-3975 |
Citations | PageRank | References |
3 | 0.47 | 10 |
Authors | ||
10 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsuhisa Yamanaka | 1 | 60 | 15.73 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Takehiro Ito | 3 | 260 | 40.71 |
| Jun Kawahara | 4 | 20 | 3.39 |
| Masashi Kiyomi | 5 | 204 | 17.45 |
| Yoshio Okamoto | 6 | 170 | 28.50 |
| Toshiki Saitoh | 7 | 87 | 14.95 |
| Akira Suzuki | 8 | 51 | 8.44 |
| Kei Uchizawa | 9 | 74 | 12.89 |
| Takeaki Uno | 10 | 1319 | 107.99 |