Name
Abstract | ||
|---|---|---|
We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to "sequentially" move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n(3)) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-53925-6_34 | WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017 |
Field | DocType | Volume |
Swap (computer programming),Discrete mathematics,Graph,Colored,Combinatorics,Vertex (geometry),Computer science,Security token | Conference | 10167 |
Issue | ISSN | Citations |
1 | 0302-9743 | 2 |
PageRank | References | Authors |
0.37 | 1 | 10 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsuhisa Yamanaka | 1 | 60 | 15.73 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Takashi Horiyama | 3 | 81 | 19.76 |
| Akitoshi Kawamura | 4 | 102 | 15.84 |
| Shin-ichi Nakano | 5 | 26 | 5.62 |
| Yoshio Okamoto | 6 | 170 | 28.50 |
| Toshiki Saitoh | 7 | 87 | 14.95 |
| Akira Suzuki | 8 | 2 | 2.74 |
| Ryuhei Uehara | 9 | 528 | 75.38 |
| Takeaki Uno | 10 | 1319 | 107.99 |