| Item type |
SIG Technical Reports(1) |
| 公開日 |
2016-02-28 |
| タイトル |
|
|
タイトル |
Sliding tokens on unicyclic graphs |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Sliding tokens on unicyclic graphs |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属 |
|
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Japan Advanced Institute of Science and Technology |
| 著者名 |
Duc, A. Hoang
Ryuhei, Uehara
|
| 著者名(英) |
Duc, A. Hoang
Ryuhei, Uehara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Given two independent sets I and J (having the same cardinality) of a graph G, and imagine that a token (coin) is placed on each vertex in I. Then, the sliding token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors such that the resulting set of vertices where tokens are placed still remains independent. Interestingly, on some graph classes such as trees, bipartite graphs, unicyclic graphs, etc., sometimes the tokens are required to make “detours” in order not to violate the independence property. This makes the sliding token problem more complicated and challenged. In this paper, based on the idea of Demaine et al. [4], we present a polynomial-time algorithm for SOLVING SLIDING TOKEN on unicyclic graphs. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Given two independent sets I and J (having the same cardinality) of a graph G, and imagine that a token (coin) is placed on each vertex in I. Then, the sliding token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors such that the resulting set of vertices where tokens are placed still remains independent. Interestingly, on some graph classes such as trees, bipartite graphs, unicyclic graphs, etc., sometimes the tokens are required to make “detours” in order not to violate the independence property. This makes the sliding token problem more complicated and challenged. In this paper, based on the idea of Demaine et al. [4], we present a polynomial-time algorithm for SOLVING SLIDING TOKEN on unicyclic graphs. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2016-AL-157,
号 5,
p. 1-7,
発行日 2016-02-28
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL16157005.pdf (660.0 kB)
