Name
Abstract | ||
|---|---|---|
Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar I-b vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-b. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I-b and I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I-b and I-r whose length (i. e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13075-0_31 | ALGORITHMS AND COMPUTATION, ISAAC 2014 |
DocType | Volume | ISSN |
Journal | 8889 | 0302-9743 |
Citations | PageRank | References |
6 | 0.52 | 14 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Martin L. Demaine | 2 | 592 | 84.37 |
| Eli Fox-Epstein | 3 | 15 | 4.53 |
| Duc L. N. Hoang | 4 | 21 | 5.76 |
| Takehiro Ito | 5 | 260 | 40.71 |
| Hirotaka Ono | 6 | 400 | 56.98 |
| Yota Otachi | 7 | 161 | 37.16 |
| Ryuhei Uehara | 8 | 528 | 75.38 |
| Takeshi Yamada | 9 | 7 | 1.23 |