{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:13Z","timestamp":1759638313358},"reference-count":20,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. &amp; Syst."],"published-print":{"date-parts":[[2019,3,1]]},"DOI":"10.1587\/transinf.2018fcp0010","type":"journal-article","created":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T17:38:54Z","timestamp":1551375534000},"page":"464-469","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Induced Tree Reconfiguration Problems"],"prefix":"10.1587","volume":"E102.D","author":[{"given":"Kunihiro","family":"WASA","sequence":"first","affiliation":[{"name":"National Institute of Informatics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsuhisa","family":"YAMANAKA","sequence":"additional","affiliation":[{"name":"Department of Systems Innovation Engineering, Faculty of Science and Engineering, Iwate University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"ARIMURA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology, Hokkaido University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] P. Bonsma, \u201cThe complexity of rerouting shortest paths,\u201d Theor. Comput. Sci., vol.510, pp.1-12, Oct. 2013. 10.1016\/j.tcs.2013.09.012","DOI":"10.1016\/j.tcs.2013.09.012"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] L. Cereceda, J. van den Heuvel, and M. Johnson, \u201cConnectedness of the graph of vertex-colourings,\u201d Discrete Math., vol.308, no.5-6, pp.913-919, March 2008. 10.1016\/j.disc.2007.07.028","DOI":"10.1016\/j.disc.2007.07.028"},{"key":"3","unstructured":"[3] R. Diestel, Graph Theory, 4th Edition, Springer, 2012."},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] R.G. Downey and M.R. Fellows, \u201cFixed-parameter tractability and completeness II: On completeness for W[1],\u201d Theor. Comput. Sci., vol.141, no.1-2, pp.109-131, April 1995. 10.1016\/0304-3975(94)00097-3","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] M. Gardner, The hypnotic fascination of sliding-block puzzles, Sci. Am., 210:122-130, 1964.","DOI":"10.1038\/scientificamerican0264-122"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] P. Gopalan, P.G. Kolaitis, E. Maneva, and C.H. Papadimitriou, \u201cThe connectivity of boolean satisfiability: computational and structural dichotomies,\u201d SIAM J. Comput., vol.38, no.6, pp.2330-2355, March 2009. 10.1137\/07070440x","DOI":"10.1137\/07070440X"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] A. Haddadan, T. Ito, A.E. Mouawad, N. Nishimura, H. Ono, A. Suzuki, and Y. Tebbal, \u201cThe complexity of dominating set reconfiguration,\u201d Theoretical Computer Science, vol.9214, pp.398-409, 2015. 10.1007\/978-3-319-21840-3_33","DOI":"10.1007\/978-3-319-21840-3_33"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] R.A. Hearn and E.D. Demaine, \u201cPSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation,\u201d Theor. Comput. Sci., vol.343, no.1-2, pp.72-96, Oct. 2005. 10.1016\/j.tcs.2005.05.008","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] T. Ito and E.D. Demaine, \u201cApproximability of the subset sum reconfiguration problem,\u201d J. Comb. Optim., vol.28, no.3, pp.639-654, 2014. 10.1007\/s10878-012-9562-z","DOI":"10.1007\/s10878-012-9562-z"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno, \u201cOn the complexity of reconfiguration problems,\u201d Theor. Comput. Sci., vol.412, no.12-14, pp.1054-1065, March 2011. 10.1016\/j.tcs.2010.12.005","DOI":"10.1016\/j.tcs.2010.12.005"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] T. Ito, M. Kami\u0144ski, and E.D. Demaine, \u201cReconfiguration of list edge-colorings in a graph,\u201d Discrete Appl. Math., vol.160, no.15, pp.2199-2207, Oct. 2012. 10.1016\/j.dam.2012.05.014","DOI":"10.1016\/j.dam.2012.05.014"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] T. Ito, K. Kawamura, H. Ono, and X. Zhou, \u201cReconfiguration of list <i>L<\/i>(2,1)-labelings in a graph,\u201d Theor. Comput. Sci., vol.544, pp.84-97, Aug. 2014. 10.1016\/j.tcs.2014.04.011","DOI":"10.1016\/j.tcs.2014.04.011"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] T. Ito, H. Ono, and Y. Otachi, \u201cReconfiguration of cliques in a graph,\u201d In Proc. 12th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol.9076, pp.212-223, Singapore, May 2015. 10.1007\/978-3-319-17142-5_19","DOI":"10.1007\/978-3-319-17142-5_19"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] M. Kami\u0144ski, P. Medvedev, and M. Milani\u010d, \u201cShortest paths between shortest paths,\u201d Theor. Comput. Sci., vol.412, no.39, pp.5205-5210, Sept. 2011. 10.1016\/j.tcs.2011.05.021","DOI":"10.1016\/j.tcs.2011.05.021"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] M. Kami\u0144ski, P. Medvedev, and M. Milani\u010d, \u201cComplexity of independent set reconfigurability problems,\u201d Theor. Comput. Sci., vol.439, pp.9-15, June 2012. 10.1016\/j.tcs.2012.03.004","DOI":"10.1016\/j.tcs.2012.03.004"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] A.E. Mouawad, N. Nishimura, V. Pathak, and V. Raman, \u201cShortest Reconfiguration Paths in the Solution Space of Boolean Formulas,\u201d In Proc. 42nd International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol.9134, pp.985-996, Kyoto, Japan, July 2015. 10.1007\/978-3-662-47672-7_80","DOI":"10.1007\/978-3-662-47672-7_80"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] A.E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki, \u201cOn the parameterized complexity of reconfiguration problems,\u201d Algorithmica, vol.78, no.1, pp.274-297, May 2017. 10.1007\/s00453-016-0159-2","DOI":"10.1007\/s00453-016-0159-2"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] W.J. Savitch, \u201cRelationships between nondeterministic and deterministic tape complexities,\u201d Journal of Computer and System Sciences, vol.4, no.2, pp.177-192, 1970. 10.1016\/s0022-0000(70)80006-x","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] M. Wrochna, \u201cReconfiguration in bounded bandwidth and tree-depth,\u201d Journal of Computer and System Sciences, vol.93, pp.1-10, 2018. 10.1016\/j.jcss.2017.11.003","DOI":"10.1016\/j.jcss.2017.11.003"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] K. Yamanaka, E.D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno, \u201cSwapping labeled tokens on graphs,\u201d Theor. Comput. Sci., vol.586, pp.81-94, June 2015. 10.1016\/j.tcs.2015.01.052","DOI":"10.1016\/j.tcs.2015.01.052"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E102.D\/3\/E102.D_2018FCP0010\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,2]],"date-time":"2019-03-02T00:27:40Z","timestamp":1551486460000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E102.D\/3\/E102.D_2018FCP0010\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2018fcp0010","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,1]]}}}