{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T01:42:23Z","timestamp":1790646143743,"version":"4.1.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T00:00:00Z","timestamp":1583798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T00:00:00Z","timestamp":1583798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1007\/s00224-020-09967-8","type":"journal-article","created":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T05:04:24Z","timestamp":1583816664000},"page":"662-686","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Token Sliding on Split Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,3,10]]},"reference":[{"key":"9967_CR1","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Bousquet, N.: Token Sliding on Chordal Graphs. In: WG 2017, Volume 10520 of Lecture Notes in Computer Science, pp. 127\u2013139 (2017)","DOI":"10.1007\/978-3-319-68705-6_10"},{"key":"9967_CR2","doi-asserted-by":"crossref","unstructured":"Bonsma, P.S., Kaminski, M., Wrochna, M.: Reconfiguring Independent Sets in Claw-Free Graphs. In: SWAT, volume 8503 of Lecture Notes in Computer Science, pp. 86\u201397. Springer (2014)","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"9967_CR3","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Mary, A., Parreau, A.: Token Jumping in Minor-Closed Classes. In: FCT, volume 10472 of Lecture Notes in Computer Science, pp. 136\u2013149. Springer (2017)","DOI":"10.1007\/978-3-662-55751-8_12"},{"key":"9967_CR4","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9967_CR5","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","volume":"600","author":"ED Demaine","year":"2015","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. Theor. Comput. Sci. 600, 132\u2013142 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"9967_CR6","doi-asserted-by":"crossref","unstructured":"Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding Token on Bipartite Permutation Graphs. In: ISAAC, volume 9472 of Lecture Notes in Computer Science, pp. 237\u2013247. Springer (2015)","DOI":"10.1007\/978-3-662-48971-0_21"},{"key":"9967_CR7","unstructured":"Hearn, R.A.: Games, puzzles, and computation. PhD Thesis, Massachusetts Institute of Technology, Cambridge (2006)"},{"issue":"1-2","key":"9967_CR8","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-2), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9967_CR9","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., Demaine, E.D.: Games, puzzles and computation. AK Peters, Massachusetts (2009)","DOI":"10.1201\/b10581"},{"key":"9967_CR10","doi-asserted-by":"crossref","unstructured":"van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pp 127\u2013160. Cambridge University Press (2013)","DOI":"10.1017\/CBO9781139506748.005"},{"key":"9967_CR11","unstructured":"Hoang, D.A., Uehara, R.: Sliding Tokens on a Cactus. In: ISAAC, volume 64 of LIPIcs, pp. 37:1\u201337:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"12\u201314","key":"9967_CR12","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. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9967_CR13","doi-asserted-by":"crossref","unstructured":"Ito, T., Kaminski, M., Ono, H., Suzuki, A., Uehara, R., Yamanaka, K.: On the Parameterized Complexity for Token Jumping on Graphs. In: TAMC, volume 8402 of Lecture Notes in Computer Science, pp. 341\u2013351. Springer (2014)","DOI":"10.1007\/978-3-319-06089-7_24"},{"key":"9967_CR14","doi-asserted-by":"crossref","unstructured":"Ito, T., Kaminski, M.J., Ono, H.: Fixed-Parameter Tractability of Token Jumping on Planar Graphs. In: ISAAC, volume 8889 of Lecture Notes in Computer Science, pp. 208\u2013219. Springer (2014)","DOI":"10.1007\/978-3-319-13075-0_17"},{"key":"9967_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2018.11.024","volume":"772","author":"T Ito","year":"2019","unstructured":"Ito, T., Otachi, Y.: Reconfiguration of colorable sets in classes of perfect graphs. Theor. Comput. Sci. 772, 111\u2013122 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"9967_CR16","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":"9967_CR17","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. In: SODA 2018, pp. 185\u2013195 (2018)","DOI":"10.1137\/1.9781611975031.13"},{"issue":"1","key":"9967_CR18","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2017","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274\u2013297 (2017)","journal-title":"Algorithmica"},{"issue":"4","key":"9967_CR19","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"N Nishimura","year":"2018","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018)","journal-title":"Algorithms"},{"key":"9967_CR20","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Massachusetts (1994)"},{"issue":"4","key":"9967_CR21","first-page":"363","volume":"1","author":"JB Saxe","year":"1980","unstructured":"Saxe, J.B.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Matrix Anal. Appl. 1(4), 363\u2013369 (1980)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9967_CR22","unstructured":"West, D.B.: Introduction to graph theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)"},{"key":"9967_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.003","volume":"93","author":"M Wrochna","year":"2018","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci. 93, 1\u201310 (2018)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09967-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09967-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09967-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,27]],"date-time":"2021-05-27T17:28:37Z","timestamp":1622136517000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09967-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,10]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["9967"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09967-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,10]]},"assertion":[{"value":"10 March 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}