{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:22:33Z","timestamp":1772119353195,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T00:00:00Z","timestamp":1724630400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s00453-024-01262-z","type":"journal-article","created":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T03:02:16Z","timestamp":1724641336000},"page":"3284-3308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Complexity of Reconfiguration of Atoms"],"prefix":"10.1007","volume":"86","author":[{"given":"Alexandre","family":"Cooper","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephanie","family":"Maaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naomi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,26]]},"reference":[{"issue":"7866","key":"1262_CR1","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1038\/s41586-021-03582-4","volume":"595","author":"S Ebadi","year":"2021","unstructured":"Ebadi, S., Wang, T.T., Levine, H., Keesling, A., Semeghini, G., Omran, A., Bluvstein, D., Samajdar, R., Pichler, H., Ho, W.W., et al.: Quantum phases of matter on a 256-atom programmable quantum simulator. Nature 595(7866), 227\u2013232 (2021)","journal-title":"Nature"},{"key":"1262_CR2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.102.063107","volume":"102","author":"KN Schymik","year":"2020","unstructured":"Schymik, K.N., Lienhard, V., Barredo, D., Scholl, P., Williams, H., Browaeys, A., Lahaye, T.: Enhanced atom-by-atom assembly of arbitrary tweezer arrays. Phys. Rev. A 102, 063107 (2020)","journal-title":"Phys. Rev. A"},{"issue":"12","key":"1262_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112553","volume":"344","author":"V Bartier","year":"2021","unstructured":"Bartier, V., Bousquet, N., Heinrich, M.: Recoloring graphs of treewidth 2. Discret. Math. 344(12), 112553 (2021)","journal-title":"Discret. Math."},{"key":"1262_CR4","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.dam.2021.05.014","volume":"301","author":"M Bonamy","year":"2021","unstructured":"Bonamy, M., Dorbec, P., Ouvrard, P.: Dominating sets reconfiguration under token sliding. Discret. Appl. Math. 301, 6\u201318 (2021)","journal-title":"Discret. Appl. Math."},{"issue":"56","key":"1262_CR5","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. Discret. Math. 308(56), 913\u2013919 (2008)","journal-title":"Discret. Math."},{"issue":"409","key":"1262_CR6","first-page":"127","volume":"2013","author":"J van den Heuvel","year":"2013","unstructured":"van den Heuvel, J.: The complexity of change. Surv. Comb. 2013(409), 127\u2013160 (2013)","journal-title":"Surv. Comb."},{"issue":"12\u201314","key":"1262_CR7","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. Theoret. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"15","key":"1262_CR8","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. Discret. Appl. Math. 160(15), 2199\u20132207 (2012)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1262_CR9","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-7:19 (2019)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"1262_CR10","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"},{"issue":"1","key":"1262_CR11","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/060652063","volume":"22","author":"G C\u0103linescu","year":"2008","unstructured":"C\u0103linescu, G., Dumitrescu, A., Pach, J.: Reconfigurations in graphs and grids. SIAM J. Discret. Math. 22(1), 124\u2013138 (2008)","journal-title":"SIAM J. Discret. Math."},{"key":"1262_CR12","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1997","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer-Verlag, New York (1997)"},{"key":"1262_CR13","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"1262_CR14","volume-title":"Oxford Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. In: Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"key":"1262_CR15","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)"},{"key":"1262_CR16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.108.023107","volume":"108","author":"B Cimring","year":"2023","unstructured":"Cimring, B., El Sabeh, R., Bacvanski, M., Maaz, S., El Hajj, I., Nishimura, N., Mouawad, A., Cooper, A.: Efficient algorithms to solve atom reconfiguration problems .I. Redistribution-reconfiguration algorithm. Phys. Rev. A. 108, 023107 (2023). https:\/\/doi.org\/10.1103\/PhysRevA.108.023107","journal-title":"Phys. Rev. A."},{"key":"1262_CR17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.108.023108","volume":"108","author":"R El Sabeh","year":"2023","unstructured":"El Sabeh, R., Bohm, J., Ding, Z., Maaz, S., Nishimura, N., El Hajj, I., Mouawad, A., Cooper, A.: Efficient algorithms to solve atom reconfiguration problems II Assignment-rerouting-ordering algorithm. Phys. Rev. A. 108, 023108 (2023). https:\/\/doi.org\/10.1103\/PhysRevA.108.023108","journal-title":"Phys. Rev. A."},{"key":"1262_CR18","volume-title":"Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. In: Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"1262_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"1262_CR20","volume-title":"Encyclopedia of Algorithms -2008 Edition","author":"N Alon","year":"2008","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color coding. In: Kao, M. (ed.) Encyclopedia of Algorithms -2008 Edition, 2008th edn. Springer, Berlin (2008)","edition":"2008"},{"key":"1262_CR21","doi-asserted-by":"crossref","unstructured":"Plehn, J., Voigt, B.: Finding minimally weighted subgraphs. In: M\u00f6hring, R.H. (ed.) Graph-Theoretic Concepts in Computer Science, In: 16rd International workshop, WG \u201990, Berlin, Germany, June 20-22, 1990, Proceedings. Lecture Notes in Computer Science, vol.\u00a0484, pp. 18\u201329. Springer (1990)","DOI":"10.1007\/3-540-53832-1_28"},{"issue":"1","key":"1262_CR22","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01262-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01262-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01262-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T03:06:50Z","timestamp":1727665610000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01262-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,26]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1262"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01262-z","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3259186\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,26]]},"assertion":[{"value":"13 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}