| Presentation | 2013-12-20 Algorithms for Independent Set Reconfiguration Problem on Graphs Erik D. DEMAINE, Martin L. DEMAINE, Takehiro ITO, Hirotaka ONO, Ryuhei UEHARA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in I_b. Then, SLIDING TOKEN is to determine whether there exists a sequence of independent sets which transforms I_b into 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 for perfect graphs. In this paper, we show that the problem is solvable in O(n) time for proper interval graphs and trivially perfect graphs, both of which are subclasses of the class of perfect graphs, where n is the number of vertices in a graph. For these graph classes, we can find an actual sequence of independent sets between I_b and I_r with the minimum number of token-slidings, in polynomial time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph algorithm / independent set / reconfiguration problem / sliding token |
| Paper # | COMP2013-39 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2013/12/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Algorithms for Independent Set Reconfiguration Problem on Graphs |
| Sub Title (in English) | |
| Keyword(1) | graph algorithm |
| Keyword(2) | independent set |
| Keyword(3) | reconfiguration problem |
| Keyword(4) | sliding token |
| 1st Author's Name | Erik D. DEMAINE |
| 1st Author's Affiliation | MIT Computer Science and Artificial Intelligence Laboratory() |
| 2nd Author's Name | Martin L. DEMAINE |
| 2nd Author's Affiliation | MIT Computer Science and Artificial Intelligence Laboratory |
| 3rd Author's Name | Takehiro ITO |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 4th Author's Name | Hirotaka ONO |
| 4th Author's Affiliation | Faculty of Economics, Kyushu University |
| 5th Author's Name | Ryuhei UEHARA |
| 5th Author's Affiliation | School of Information Science, JAIST |
| Date | 2013-12-20 |
| Paper # | COMP2013-39 |
| Volume (vol) | vol.113 |
| Number (no) | 371 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |