WEKO3
アイテム
Complexity of Hamiltonian Cycle Reconfiguration
http://hdl.handle.net/10258/00010207
http://hdl.handle.net/10258/000102073a0f065e-bae3-4d5c-9b99-5e3379975ab9
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
ALGO_11_9 (323.7 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article.(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-06-25 | |||||||||||||
| 書誌情報 |
en : algorithms 巻 11, 号 9, 発行日 2018 |
|||||||||||||
| タイトル | ||||||||||||||
| タイトル | Complexity of Hamiltonian Cycle Reconfiguration | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | bipartite permutation graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | chordal bipartite graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | combinatorial reconfiguration | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Hamiltonian cycle | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | PSPACE-complete | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | split graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | strongly chordal graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | unit interval graphs | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| アクセス権 | ||||||||||||||
| アクセス権 | open access | |||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||
| 著者 |
髙岡, 旭
× 髙岡, 旭
|
|||||||||||||
| 室蘭工業大学研究者データベースへのリンク | ||||||||||||||
| 表示名 | 髙岡 旭（TAKAOKA Asahi） | |||||||||||||
| URL | http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html | |||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | The Hamiltonian cycle reconfiguration problem asks, given two Hamiltonian cycles C0 and Ct of a graph G, whether there is a sequence of Hamiltonian cycles C0, C1, . . ., Ct such that Ci can be obtained from Ci_1 by a switch for each i with 1≦i≦ t, where a switch is the replacement of a pair of edges uv and wz on a Hamiltonian cycle with the edges uw and vz of G, given that uw and vz did not appear on the cycle. We show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete, settling an open question posed by Ito et al. (2011) and van den Heuvel (2013). More precisely, we show that the Hamiltonian cycle reconfiguration problem is PSPACE-complete for chordal bipartite graphs, strongly chordal split graphs, and bipartite graphs with maximum degree 6. Bipartite permutation graphs form a proper subclass of chordal bipartite graphs, and unit interval graphs form a proper subclass of strongly chordal graphs. On the positive side, we show that, for any two Hamiltonian cycles of a bipartite permutation graph and a unit interval graph, there is a sequence of switches transforming one cycle to the other, and such a sequence can be obtained in linear time. | |||||||||||||
| 言語 | en | |||||||||||||
| 出版者 | ||||||||||||||
| 出版者 | MDPI | |||||||||||||
| 言語 | en | |||||||||||||
| 出版者版へのリンク | ||||||||||||||
| 表示名 | 10.3390/a11090140 | |||||||||||||
| URL | https://doi.org/10.3390/a11090140 | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | 10.3390/a11090140 | |||||||||||||
| 日本十進分類法 | ||||||||||||||
| 主題Scheme | NDC | |||||||||||||
| 主題 | 548 | |||||||||||||
| 権利 | ||||||||||||||
| 言語 | en | |||||||||||||
| 権利情報 | ©2018 by the authors; licensee MDPI AG, Basel, Switzerland. This article is an open-access article distributed under the terms and conditions of the Creative Commons Attribution License(http://creativecommons.org/licenses/by/4.0/) | |||||||||||||
| 著者版フラグ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| フォーマット | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | application/pdf | |||||||||||||
