{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:47:18Z","timestamp":1769561238686,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s00453-021-00848-1","type":"journal-article","created":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T10:03:12Z","timestamp":1625738592000},"page":"2914-2951","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On Girth and the Parameterized Complexity of Token Sliding and Token Jumping"],"prefix":"10.1007","volume":"83","author":[{"given":"Valentin","family":"Bartier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9522-3770","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Dallard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Lomer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"key":"848_CR1","doi-asserted-by":"publisher","unstructured":"Bartier, V., Bousquet, N., Dallard, C., Lomer, K., Mouawad, A.E.: On girth and the parameterized complexity of token sliding and token jumping. In: 31st International Symposium on Algorithms and Computation (ISAAC 2020), vol. 181, pp. 44:1\u201344:17. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.44","DOI":"10.4230\/LIPIcs.ISAAC.2020.44"},{"key":"848_CR2","doi-asserted-by":"publisher","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13\u201316, 2019, Berlin, Germany, pp. 13:1\u201313:17 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.13","DOI":"10.4230\/LIPIcs.STACS.2019.13"},{"key":"848_CR3","doi-asserted-by":"crossref","unstructured":"Bonamy, M., Bousquet, N.: Token sliding on chordal graphs. CoRR (2016). arXiv:1605.00442","DOI":"10.1007\/978-3-319-68705-6_10"},{"key":"848_CR4","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Bousquet, N., Charbit, P., Thomass\u00e9, S., Watrigant, R.: Parameterized complexity of independent set in H-free graphs. In: Paul, C., Pilipczuk, M. (eds.), 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20\u201324, 2018, Helsinki, Finland, LIPIcs, vol. 115, pp. 17:1\u201317:13. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2018.17","DOI":"10.4230\/LIPIcs.IPEC.2018.17"},{"key":"848_CR5","doi-asserted-by":"crossref","unstructured":"Bonsma, P.S., Kaminski, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. In: Algorithm Theory\u2014SWAT 2014\u201414th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2\u20134, 2014. Proceedings, pp. 86\u201397 (2014)","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"848_CR6","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Mary, A., Parreau, A.: Token jumping in minor-closed classes. In: Fundamentals of Computation Theory\u201421st International Symposium, FCT 2017, Bordeaux, France, September 11\u201313, 2017, Proceedings, pp. 136\u2013149 (2017). https:\/\/doi.org\/10.1007\/978-3-662-55751-8_12","DOI":"10.1007\/978-3-662-55751-8_12"},{"key":"848_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.05.015","volume":"639","author":"RC Brewster","year":"2016","unstructured":"Brewster, R.C., McGuinness, S., Moore, B., Noel, J.A.: A dichotomy theorem for circular colouring reconfiguration. Theor. Comput. Sci. 639, 1\u201313 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"56","key":"848_CR8","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(56), 913\u2013919 (2008)","journal-title":"Discrete Math."},{"key":"848_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"848_CR10","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Demaine, M.L., Fox-Epstein, E., Hoang, D.A., Ito, T., Ono, H., Otachi, Y., Uehara, R., Yamada, T.: Polynomial-time algorithm for sliding tokens on trees. In: Algorithms and Computation. Lecture Notes in Computer Science, vol. 8889, pp. 389\u2013400. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13075-0_31","DOI":"10.1007\/978-3-319-13075-0_31"},{"key":"848_CR11","doi-asserted-by":"crossref","unstructured":"Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding token on bipartite permutation graphs. In: Algorithms and Computation\u201426th International Symposium, ISAAC 2015, Nagoya, Japan, December 9\u201311, 2015, Proceedings, pp. 237\u2013247 (2015)","DOI":"10.1007\/978-3-662-48971-0_21"},{"key":"848_CR12","doi-asserted-by":"publisher","unstructured":"Gharibian, S., Sikora, J.: Ground state connectivity of local Hamiltonians. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 617\u2013628 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47672-7_50","DOI":"10.1007\/978-3-662-47672-7_50"},{"issue":"6","key":"848_CR13","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. Comput. 38(6), 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"848_CR14","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). https:\/\/doi.org\/10.1016\/j.tcs.2005.05.008","journal-title":"Theor. Comput. Sci."},{"issue":"12\u201314","key":"848_CR15","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). https:\/\/doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theor. Comput. Sci."},{"issue":"15","key":"848_CR16","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":"848_CR17","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: Theory and Applications of Models of Computation\u201411th Annual Conference, TAMC 2014, Chennai, India, April 11\u201313, 2014. Proceedings, pp. 341\u2013351 (2014)","DOI":"10.1007\/978-3-319-06089-7_24"},{"key":"848_CR18","doi-asserted-by":"crossref","unstructured":"Ito, T., Kami$$\\acute{n}$$ski, M., Ono, H.: Fixed-parameter tractability of token jumping on planar graphs. In: Algorithms and Computation, Lecture Notes in Computer Science, pp. 208\u2013219. Springer (2014)","DOI":"10.1007\/978-3-319-13075-0_17"},{"issue":"3","key":"848_CR19","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1587\/transinf.2015FCP0010","volume":"99\u2013D","author":"T Ito","year":"2016","unstructured":"Ito, T., Nooka, H., Zhou, X.: Reconfiguration of vertex covers in a graph. IEICE Trans. 99\u2013D(3), 598\u2013606 (2016)","journal-title":"IEICE Trans."},{"issue":"4","key":"848_CR20","doi-asserted-by":"publisher","first-page":"397","DOI":"10.2307\/2369492","volume":"2","author":"WW Johnson","year":"1879","unstructured":"Johnson, W.W., Story, W.E.: Notes on the \u201c15\u201d puzzle. Am. J. Math. 2(4), 397\u2013404 (1879)","journal-title":"Am. J. Math."},{"key":"848_CR21","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"M Kaminski","year":"2012","unstructured":"Kaminski, M., Medvedev, P., Milanic, M.: Complexity of independent set reconfigurability problems. Theor. Comput. Sci. 439, 9\u201315 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.004","journal-title":"Theor. Comput. Sci."},{"key":"848_CR22","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":"848_CR23","doi-asserted-by":"crossref","unstructured":"Kendall, G., Parkes, A.J., Spoerer, K.: A survey of NP-complete puzzles. ICGA J. 13\u201334 (2008)","DOI":"10.3233\/ICG-2008-31103"},{"issue":"3","key":"848_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/rsa.3240070302","volume":"7","author":"JH Kim","year":"1995","unstructured":"Kim, J.H.: The Ramsey number $$R(3, t)$$ has order of magnitude $$t^2\/\\log t$$. Random Struct. Algorithms 7(3), 173\u2013207 (1995). https:\/\/doi.org\/10.1002\/rsa.3240070302","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"848_CR25","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3280825","volume":"15","author":"D Lokshtanov","year":"2019","unstructured":"Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms 15(1), 7:1\u20137:19 (2019). https:\/\/doi.org\/10.1145\/3280825","journal-title":"ACM Trans. Algorithms"},{"key":"848_CR26","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M.S., Saurabh, S.: Reconfiguration on sparse graphs. In: Algorithms and Data Structures\u201414th International Symposium, WADS 2015, Victoria, BC, Canada, August 5\u20137, 2015. Proceedings, pp. 506\u2013517 (2015)","DOI":"10.1007\/978-3-319-21840-3_42"},{"key":"848_CR27","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"A Lubiw","year":"2015","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17\u201323 (2015). https:\/\/doi.org\/10.1016\/j.comgeo.2014.11.001","journal-title":"Comput. Geom."},{"key":"848_CR28","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Pathak, V., Raman, V.: Shortest reconfiguration paths in the solution space of Boolean formulas. In: Automata, Languages, and Programming\u201442nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 985\u2013996 (2015)","DOI":"10.1007\/978-3-662-47672-7_80"},{"key":"848_CR29","doi-asserted-by":"crossref","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. In: Algorithms and Computation\u201425th International Symposium, ISAAC 2014, Jeonju, Korea, December 15\u201317, 2014, Proceedings, pp. 452\u2013463 (2014)","DOI":"10.1007\/978-3-319-13075-0_36"},{"issue":"4","key":"848_CR30","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). https:\/\/doi.org\/10.3390\/a11040052","journal-title":"Algorithms"},{"issue":"409","key":"848_CR31","first-page":"127","volume":"2013","author":"J van den Heuvel","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surv. Combin. 2013(409), 127\u2013160 (2013)","journal-title":"Surv. Combin."},{"key":"848_CR32","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and tree depth. CoRR (2014). arXiv:1405.0847"},{"key":"848_CR33","unstructured":"Wrochna, M.: Homomorphism reconfiguration via homotopy. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4\u20137, 2015, Garching, Germany, pp. 730\u2013742 (2015)"},{"issue":"1","key":"848_CR34","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007). https:\/\/doi.org\/10.4086\/toc.2007.v003a006","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00848-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00848-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00848-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:07:46Z","timestamp":1628161666000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00848-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,8]]},"references-count":34,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["848"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00848-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,8]]},"assertion":[{"value":"30 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}