{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T21:40:03Z","timestamp":1768513203109,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319130743","type":"print"},{"value":"9783319130750","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_31","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"389-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Polynomial-Time Algorithm for Sliding Tokens on Trees"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin L.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eli","family":"Fox-Epstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Duc A.","family":"Hoang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takehiro","family":"Ito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Yamada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$ -arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/s10878-012-9490-y","volume":"27","author":"M Bonamy","year":"2014","unstructured":"Bonamy, M., Johnson, M., Lignos, I., Patel, V., Paulusma, D.: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J. Combinatorial Optimization 27, 132\u2013143 (2014)","journal-title":"J. Combinatorial Optimization"},{"key":"31_CR3","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. Theoretical Computer Science 510, 1\u201312 (2013)","journal-title":"Theoretical Computer Science"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Bonsma, P.: Independent set reconfiguration in cographs. To appear in WG 2014, arXiv:1402.1587 (2014)","DOI":"10.1007\/978-3-319-12340-0_9"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma, P., Cereceda, L.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science 410, 5215\u20135226 (2009)","journal-title":"Theoretical Computer Science"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-319-08404-6_8","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"P Bonsma","year":"2014","unstructured":"Bonsma, P., Kami\u0144ski, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 86\u201397. Springer, Heidelberg (2014)"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Demaine, M.L., Fox-Epstein, E., Hoang, D.A., Ito, T., Ono, H., Otachi, Y., Uehara, R., Yamada, T.: Linear-time algorithm for sliding tokens on trees arXiv:1406.6576 (2014)","DOI":"10.1007\/978-3-319-13075-0_31"},{"key":"31_CR8","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.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Computing 38, 2330\u20132355 (2009)","journal-title":"SIAM J. Computing"},{"key":"31_CR9","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. Theoretical Computer Science 343, 72\u201396 (2005)","journal-title":"Theoretical Computer Science"},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. A K Peters (2009)","DOI":"10.1201\/b10581"},{"key":"31_CR11","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.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theoretical Computer Science 412, 1054\u20131065 (2011)","journal-title":"Theoretical Computer Science"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-06089-7_24","volume-title":"Theory and Applications of Models of Computation","author":"T Ito","year":"2014","unstructured":"Ito, T., Kami\u0144ski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the parameterized complexity for token jumping on graphs. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 341\u2013351. Springer, Heidelberg (2014)"},{"key":"31_CR13","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 $$L(2,1)$$ -labelings in a graph. Theoretical Computer Science 544, 84\u201397 (2014)","journal-title":"Theoretical Computer Science"},{"key":"31_CR14","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. Theoretical Computer Science 412, 5205\u20135210 (2011)","journal-title":"Theoretical Computer Science"},{"key":"31_CR15","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, M., Milani\u010d, M.: Complexity of independent set reconfigurability problems. Theoretical Computer Science 439, 9\u201315 (2012)","journal-title":"Theoretical Computer Science"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"4613","DOI":"10.1016\/j.tcs.2011.04.041","volume":"412","author":"K Makino","year":"2011","unstructured":"Makino, K., Tamaki, S., Yamamoto, M.: An exact algorithm for the Boolean connectivity problem for $$k$$ -CNF. Theoretical Computer Science 412, 4613\u20134618 (2011)","journal-title":"Theoretical Computer Science"},{"key":"31_CR17","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":"31_CR18","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions arXiv:1405.2447"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"van den Heuvel, J.: The complexity of change. Surveys in Combinatorics 2013, London Mathematical Society Lecture Notes Series 409 (2013)","DOI":"10.1017\/CBO9781139506748.005"},{"key":"31_CR20","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth arXiv:1405.0847 (2014)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T04:39:57Z","timestamp":1689655197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}