@article{oai:muroran-it.repo.nii.ac.jp:00010266,
 author = {髙岡, 旭 and TAKAOKA, Asahi},
 issue = {9},
 journal = {algorithms},
 month = {},
 note = {application/pdf, 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.},
 title = {Complexity of Hamiltonian Cycle Reconfiguration},
 volume = {11},
 year = {2018},
 yomi = {タカオカ, アサヒ}
}