{"created":"2023-06-19T10:30:05.965732+00:00","id":10266,"links":{},"metadata":{"_buckets":{"deposit":"3e2d3ab8-98fc-4bf6-b4ea-974a96cc81ab"},"_deposit":{"created_by":18,"id":"10266","owners":[18],"pid":{"revision_id":0,"type":"depid","value":"10266"},"status":"published"},"_oai":{"id":"oai:muroran-it.repo.nii.ac.jp:00010266","sets":["216:489","46"]},"author_link":["59462"],"item_79_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2018","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"9","bibliographicVolumeNumber":"11","bibliographic_titles":[{"bibliographic_title":"algorithms","bibliographic_titleLang":"en"}]}]},"item_79_description_23":{"attribute_name":"フォーマット","attribute_value_mlt":[{"subitem_description":"application/pdf","subitem_description_type":"Other"}]},"item_79_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_79_link_17":{"attribute_name":"出版者版へのリンク","attribute_value_mlt":[{"subitem_link_text":"10.3390/a11090140","subitem_link_url":"https://doi.org/10.3390/a11090140"}]},"item_79_link_5":{"attribute_name":"室蘭工業大学研究者データベースへのリンク","attribute_value_mlt":[{"subitem_link_text":"髙岡 旭（TAKAOKA Asahi）","subitem_link_url":"http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html"}]},"item_79_publisher_11":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"MDPI","subitem_publisher_language":"en"}]},"item_79_relation_18":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"10.3390/a11090140","subitem_relation_type_select":"DOI"}}]},"item_79_rights_19":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"©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/)","subitem_rights_language":"en"}]},"item_79_subject_9":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"548","subitem_subject_scheme":"NDC"}]},"item_79_version_type_21":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorAffiliations":[{"affiliationNameIdentifiers":[{}],"affiliationNames":[{},{}]}],"creatorNames":[{"creatorName":"髙岡, 旭","creatorNameLang":"ja"},{"creatorName":"TAKAOKA, Asahi","creatorNameLang":"en"},{"creatorName":"タカオカ, アサヒ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2020-06-25"}],"displaytype":"detail","filename":"ALGO_11_9.pdf","filesize":[{"value":"323.7 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"ALGO_11_9","objectType":"fulltext","url":"https://muroran-it.repo.nii.ac.jp/record/10266/files/ALGO_11_9.pdf"},"version_id":"cb456b7e-8fae-45bc-bd89-974b908a5051"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"bipartite permutation graphs","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"chordal bipartite graphs","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"combinatorial reconfiguration","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Hamiltonian cycle","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"PSPACE-complete","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"split graphs","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"strongly chordal graphs","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"unit interval graphs","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Complexity of Hamiltonian Cycle Reconfiguration","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Complexity of Hamiltonian Cycle Reconfiguration","subitem_title_language":"en"}]},"item_type_id":"79","owner":"18","path":["46","489"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2020-06-25"},"publish_date":"2020-06-25","publish_status":"0","recid":"10266","relation_version_is_last":true,"title":["Complexity of Hamiltonian Cycle Reconfiguration"],"weko_creator_id":"18","weko_shared_id":-1},"updated":"2023-10-24T01:35:56.981784+00:00"}