{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T02:51:57Z","timestamp":1725850317957},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319299990"},{"type":"electronic","value":"9783319300009"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-30000-9_26","type":"book-chapter","created":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T21:45:50Z","timestamp":1456436750000},"page":"330-342","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Induced Tree Reconfiguration Problems"],"prefix":"10.1007","author":[{"given":"Kunihiro","family":"Wasa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsuhisa","family":"Yamanaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"Arimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,26]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2013.09.012","volume":"510","author":"P Bonsma","year":"2013","unstructured":"Bonsma, P.: The complexity of rerouting shortest paths. Theor. Comput. Sci. 510, 1\u201312 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"5\u20136","key":"26_CR2","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","volume":"308","author":"L Cereceda","year":"2008","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Math. 308(5\u20136), 913\u2013919 (2008)","journal-title":"Discrete Math."},{"key":"26_CR3","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"issue":"1\u20132","key":"26_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1\u20132), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1038\/scientificamerican0264-122","volume":"210","author":"M Gardner","year":"1964","unstructured":"Gardner, M.: The hypnotic fascination of sliding-block puzzles. Sci. Am. 210, 122\u2013130 (1964)","journal-title":"Sci. Am."},{"issue":"6","key":"26_CR6","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E., Papadimitriou, C.H.: The connectivity of boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"26_CR7","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"RA Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"26_CR8","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/s10878-012-9562-z","volume":"28","author":"T Ito","year":"2012","unstructured":"Ito, T., Demaine, E.D.: Approximability of the subset sum reconfiguration problem. J. Comb. Optim. 28(3), 639\u2013654 (2012)","journal-title":"J. Comb. Optim."},{"issue":"12\u201314","key":"26_CR9","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"15","key":"26_CR10","doi-asserted-by":"publisher","first-page":"2199","DOI":"10.1016\/j.dam.2012.05.014","volume":"160","author":"T Ito","year":"2012","unstructured":"Ito, T., Kami\u0144ski, M., Demaine, E.D.: Reconfiguration of list edge-colorings in a graph. Discrete Appl. Math. 160(15), 2199\u20132207 (2012)","journal-title":"Discrete Appl. Math."},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.tcs.2014.04.011","volume":"544","author":"T Ito","year":"2014","unstructured":"Ito, T., Kawamura, K., Ono, H., Zhou, X.: Reconfiguration of list \n                      \n                        \n                      \n                      $${L}(2,1)$$\n                      \n                        \n                          \n                            L\n                            (\n                            2\n                            ,\n                            1\n                            )\n                          \n                        \n                      \n                    -labelings in a graph. Theor. Comput. Sci. 544, 84\u201397 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-319-17142-5_19","volume-title":"Theory and Applications of Models of Computation","author":"T Ito","year":"2015","unstructured":"Ito, T., Ono, H., Otachi, Y.: Reconfiguration of cliques in a graph. In: Jain, R., Jain, S., Stephan, F. (eds.) TAMC 2015. LNCS, vol. 9076, pp. 212\u2013223. Springer, Heidelberg (2015)"},{"issue":"39","key":"26_CR13","doi-asserted-by":"publisher","first-page":"5205","DOI":"10.1016\/j.tcs.2011.05.021","volume":"412","author":"M Kami\u0144ski","year":"2011","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Shortest paths between shortest paths. Theor. Comput. Sci. 412(39), 5205\u20135210 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski, M., Medvedev, P., Milani\u010d, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9\u201315 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1007\/978-3-662-47672-7_80","volume-title":"Automata, Languages, and Programming","author":"AE Mouawad","year":"2015","unstructured":"Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V.: Shortest reconfiguration paths in the solution space of Boolean formulas. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 985\u2013996. Springer, Heidelberg (2015)"},{"key":"26_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-319-03898-8_24","volume-title":"Parameterized and Exact Computation","author":"AE Mouawad","year":"2013","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 281\u2013294. Springer, Heidelberg (2013)"},{"key":"26_CR17","first-page":"216","volume":"1978","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. STOC 1978, 216\u2013226 (1978)","journal-title":"STOC"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.tcs.2015.01.052","volume":"586","author":"K Yamanaka","year":"2015","unstructured":"Yamanaka, K., Demaine, E.D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K., Uno, T.: Swapping labeled tokens on graphs. Theor. Comput. Sci. 586, 81\u201394 (2015)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-30000-9_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T16:02:54Z","timestamp":1559404974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-30000-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319299990","9783319300009"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-30000-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}