|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/13768
|
| タイトル: | Swapping Colored Tokens on Graphs |
| 著者: | Yamanaka, Katsuhisa
Horiyama, Takashi
Kirkpatrick, David
Otachi, Yota
Saitoh, Toshiki
Uehara, Ryuhei
Uno, Yushi |
| キーワード: | reconfiguration problem
swapping colored token
graph class
NP-completeness
polynomial tiem algorithm |
| 発行日: | 2015-08-05 |
| 出版者: | Springer |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 9214 |
| 開始ページ: | 619 |
| 終了ページ: | 628 |
| DOI: | 10.1007/978-3-319-21840-3_51 |
| 抄録: | We investigate the computational complexity of the followingproblem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform as small numbers of swappings as possible so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,...,c}, we call this problem c-Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-Colored Token Swapping is NP-complete for every constant c>3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs and in linear time for trees. |
| Rights: | This is the author-created version of Springer, Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara and Yushi Uno, Lecture Notes in Computer Science, 9214, 2015, 619-628. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-319-21840-3_51 |
| URI: | http://hdl.handle.net/10119/13768 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 21475.pdf | | 90Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
