{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:23Z","timestamp":1770921383465,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_1","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:55Z","timestamp":1770918775000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Complexity of\u00a0Constrained Reconfiguration and\u00a0Motion Planning"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[]},{"given":"Remy","family":"El Sabeh","sequence":"additional","affiliation":[]},{"given":"Amer\u00a0E.","family":"Mouawad","sequence":"additional","affiliation":[]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"1_CR1","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. GTM, vol. 184. Springer, New York (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0619-4"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Hommelsheim, F., Kobayashi, Y., M\u00fchlenthaler, M., Suzuki, A.: Feedback vertex set reconfiguration in planar graphs. Theor. Comput. Sci. 979, 114,188 (2023)","DOI":"10.1016\/j.tcs.2023.114188"},{"key":"1_CR3","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Mouawad, A.E., Nishimura, N., Siebertz, S.: A survey on the parameterized complexity of reconfiguration problems. Comput. Sci. Rev. 53, 100,663 (2024). https:\/\/doi.org\/10.1016\/J.COSREV.2024.100663","DOI":"10.1016\/J.COSREV.2024.100663"},{"key":"1_CR4","unstructured":"Bousquet, N., Sabeh, R.E., Mouawad, A.E., Nishimura, N.: On the complexity of constrained reconfiguration and motion planning (2025). https:\/\/arxiv.org\/abs\/2508.13032"},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Brianski, M., Felsner, S., Hodor, J., Micek, P.: Reconfiguring independent sets on interval graphs. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, 23\u201327 August 2021. LIPIcs, vol. 202, pp. 23:1\u201323:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2021.23","DOI":"10.4230\/LIPICS.MFCS.2021.23"},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Buchin, K., Hagedoorn, M., Kostitsyna, I., van Mulken, M.: Dots & boxes is PSPACE-complete. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, 23\u201327 August 2021. LIPIcs, vol. 202, pp. 25:1\u201325:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2021.25","DOI":"10.4230\/LIPICS.MFCS.2021.25"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"PZ Chinn","year":"1982","unstructured":"Chinn, P.Z., Chv\u00e1talov\u00e1, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices\u2013a survey. J. Graph Theory 6(3), 223\u2013254 (1982)","journal-title":"J. Graph Theory"},{"key":"1_CR8","series-title":"IFIP Advances in Information and Communication Technology","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-11628-5_18","volume-title":"Emerging Trends in Technological Innovation","author":"P \u0106urkovi\u0107","year":"2010","unstructured":"\u0106urkovi\u0107, P., Jerbi\u0107, B.: Dual-arm robot motion planning based on cooperative coevolution. In: Camarinha-Matos, L.M., Pereira, P., Ribeiro, L. (eds.) DoCEIS 2010. IAICT, vol. 314, pp. 169\u2013178. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11628-5_18"},{"key":"1_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., et al.: Parameterized Algorithms, vol. 5. Springer, Cham (2015)"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/3-540-45071-8_36","volume-title":"Computing and Combinatorics","author":"ED Demaine","year":"2003","unstructured":"Demaine, E.D., Hohenberger, S., Liben-Nowell, D.: Tetris is hard, even to approximate. In: Warnow, T., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 351\u2013363. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45071-8_36"},{"key":"1_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-70107-2","volume-title":"Graph Theory","author":"R Diestel","year":"2025","unstructured":"Diestel, R.: Graph Theory, vol. 173. Springer, Cham (2025)"},{"issue":"1\u20132","key":"1_CR12","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. Theoret. Comput. Sci. 343(1\u20132), 72\u201396 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. CRC Press (2009)","DOI":"10.1201\/b10581"},{"key":"1_CR14","unstructured":"van\u00a0den Heuvel, J.: The Complexity of change, p. 409. Part of London Mathematical Society Lecture Note Series (2013)"},{"key":"1_CR15","doi-asserted-by":"publisher","unstructured":"Hue, L.T., Anh, N.P.T.: Planning the optimal trajectory for a dual-arm robot system using a genetic algorithm considering the controller. In: 2022 International Conference on Advanced Technologies for Communications (ATC), pp. 292\u2013297 (2022). https:\/\/doi.org\/10.1109\/ATC55345.2022.9942975","DOI":"10.1109\/ATC55345.2022.9942975"},{"issue":"12\u201314","key":"1_CR16","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., et al.: On the complexity of reconfiguration problems. Theoret. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"1_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discret. Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discret. Math."},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-319-13524-3_21","volume-title":"Parameterized and Exact Computation","author":"AE Mouawad","year":"2014","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions. In: Cygan, M., Heggernes, P. (eds.) IPEC 2014. LNCS, vol. 8894, pp. 246\u2013257. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13524-3_21"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/a11040052","DOI":"10.3390\/a11040052"},{"key":"1_CR20","doi-asserted-by":"publisher","unstructured":"Ohsaka, N.: Gap preserving reductions between reconfiguration problems. In: Berenbrink, P., Bouyer, P., Dawar, A., Kant\u00e9, M.M. (eds.) 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, Hamburg, Germany, 7\u20139 March 2023. LIPIcs, vol. 254, pp. 49:1\u201349:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2023.49","DOI":"10.4230\/LIPICS.STACS.2023.49"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Ohsaka, N.: Gap amplification for reconfiguration problems. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pp. 1345\u20131366. SIAM (2024)","DOI":"10.1137\/1.9781611977912.54"},{"issue":"10","key":"1_CR22","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1177\/0278364918765952","volume":"37","author":"SSM Salehian","year":"2018","unstructured":"Salehian, S.S.M., Figueroa, N., Billard, A.: A unified framework for coordinated multi-arm motion planning. Int. J. Robot. Res. 37(10), 1205\u20131232 (2018). https:\/\/doi.org\/10.1177\/0278364918765952","journal-title":"Int. J. Robot. Res."},{"key":"1_CR23","unstructured":"Tippenhauer, S., Muzler, W.: On planar 3-SAT and its variants. Fachbereich Mathematik und Informatik der Freien Universitat Berlin (2016)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:58Z","timestamp":1770918778000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}