{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T04:12:31Z","timestamp":1778818351082,"version":"3.51.4"},"reference-count":37,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.tcs.2026.115963","type":"journal-article","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T07:17:09Z","timestamp":1776237429000},"page":"115963","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["On the complexity of finding central configurations of the graph-generalized (n2\u22121)-puzzle"],"prefix":"10.1016","volume":"1076","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7724-8990","authenticated-orcid":false,"given":"Martijn","family":"van Ee","sequence":"first","affiliation":[]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.tcs.2026.115963_bib0001","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","article-title":"The (n2\u22121)-puzzle and related relocation problems","volume":"10","author":"Ratner","year":"1990","journal-title":"J. Symb. Comput."},{"issue":"4","key":"10.1016\/j.tcs.2026.115963_bib0002","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/2369492","article-title":"Notes on the \u201c15\u201d puzzle","volume":"2","author":"Johnson","year":"1879","journal-title":"Am. J. Math."},{"key":"10.1016\/j.tcs.2026.115963_bib0003","series-title":"Mathematical Puzzles of Sam Loyd","author":"Loyd","year":"1959"},{"key":"10.1016\/j.tcs.2026.115963_bib0004","first-page":"127","article-title":"The complexity of change","volume":"409","author":"van den Heuvel","year":"2013","journal-title":"Surv. Comb."},{"issue":"4","key":"10.1016\/j.tcs.2026.115963_bib0005","doi-asserted-by":"crossref","first-page":"52","DOI":"10.3390\/a11040052","article-title":"Introduction to reconfiguration","volume":"11","author":"Nishimura","year":"2018","journal-title":"Algorithms"},{"issue":"1","key":"10.1016\/j.tcs.2026.115963_bib0006","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","article-title":"Graph puzzles, homotopy, and the alternating group","volume":"16","author":"Wilson","year":"1974","journal-title":"J. Comb. Theory Ser. B"},{"key":"10.1016\/j.tcs.2026.115963_bib0007","series-title":"Proceedings of the 25th Annual Symposium on Foundations of Computer Science","first-page":"241","article-title":"Coordinating pebble motion on graphs, the diameter of permutation groups, and applications","author":"Kornhauser","year":"1984"},{"key":"10.1016\/j.tcs.2026.115963_bib0008","series-title":"Connectivity Properties of Some Transformation Graphs","author":"Trakultraipruk","year":"2013"},{"key":"10.1016\/j.tcs.2026.115963_bib0009","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2018.04.031","article-title":"A simple proof that the (n2\u22121)-puzzle is hard","volume":"732","author":"Demaine","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115963_bib0010","series-title":"Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation","first-page":"1","article-title":"Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard","author":"Goldreich","year":"2011"},{"key":"10.1016\/j.tcs.2026.115963_bib0011","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-003-1028-3","article-title":"Fixed-parameter algorithms for closest string and related problems","volume":"37","author":"Gramm","year":"2003","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.115963_bib0012","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02679443","article-title":"On covering problems of codes","volume":"30","author":"Frances","year":"1997","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"10.1016\/j.tcs.2026.115963_bib0013","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","article-title":"Distinguishing string selection problems","volume":"185","author":"Lanctot","year":"2003","journal-title":"Inf. Comput."},{"issue":"2\u20134","key":"10.1016\/j.tcs.2026.115963_bib0014","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.jda.2004.08.015","article-title":"Hardness results for the center and median string problems under the weighted and unweighted edit distances","volume":"3","author":"Nicolas","year":"2005","journal-title":"J. Discrete Algoritms"},{"issue":"12\u201314","key":"10.1016\/j.tcs.2026.115963_bib0015","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1016\/j.tcs.2010.12.009","article-title":"The transposition median problem is NP-complete","volume":"412","author":"Bader","year":"2011","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2026.115963_bib0016","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","article-title":"The reversal median problem","volume":"15","author":"Caprara","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"10.1016\/j.tcs.2026.115963_bib0017","unstructured":"L. Cunha, T. Lopes, A. Mary, Complexity and algorithms for Swap median and relation to other consensus problems, (2024a). arXiv: 2409.09734."},{"issue":"1","key":"10.1016\/j.tcs.2026.115963_bib0018","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1186\/s13015-024-00269-z","article-title":"On the parameterized complexity of the median and closest problems under some permutation metrics","volume":"19","author":"Cunha","year":"2024","journal-title":"Algorithms Mol. Biol."},{"key":"10.1016\/j.tcs.2026.115963_bib0019","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.dam.2019.04.002","article-title":"On the computational complexity of closest genome problems","volume":"274","author":"Cunha","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115963_bib0020","series-title":"Elec. Colloq. on Comput. Complexity","article-title":"The median problems for breakpoints are NP-complete","volume":"71","author":"Pe\u2019er","year":"1998"},{"issue":"1-3","key":"10.1016\/j.tcs.2026.115963_bib0021","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2007.05.029","article-title":"Multiple genome rearrangement by swaps and by element duplications","volume":"385","author":"Popov","year":"2007","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115963_bib0022","doi-asserted-by":"crossref","first-page":"1854","DOI":"10.1137\/19M1255781","article-title":"Tight hardness results for consensus problems on circular strings and time series","volume":"34","author":"Bulteau","year":"2020","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.tcs.2026.115963_bib0023","series-title":"48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)","first-page":"54:1","article-title":"On the complexity of computing time series medians under the move-split-merge metric","author":"Holznigenkemper","year":"2023"},{"key":"10.1016\/j.tcs.2026.115963_bib0024","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972","journal-title":"Complexity Comput. Comput."},{"key":"10.1016\/j.tcs.2026.115963_bib0025","series-title":"Network Flows","author":"Ahuja","year":"1988"},{"issue":"1-2","key":"10.1016\/j.tcs.2026.115963_bib0026","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Nav. Res. Logist. Q."},{"issue":"2","key":"10.1016\/j.tcs.2026.115963_bib0027","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","article-title":"A matching problem with side conditions","volume":"29","author":"Cornu\u00e9jols","year":"1980","journal-title":"Discrete Math."},{"key":"10.1016\/j.tcs.2026.115963_bib0028","series-title":"Extensions of Matching Theory","author":"Hartvigsen","year":"1984"},{"issue":"6","key":"10.1016\/j.tcs.2026.115963_bib0029","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1016\/j.orl.2004.12.002","article-title":"Complexity of the min\u2013max and min\u2013max regret assignment problems","volume":"33","author":"Aissi","year":"2005","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/j.tcs.2026.115963_bib0030","series-title":"Robust Discrete Optimization and its Applications","author":"Kouvelis","year":"2013"},{"issue":"2","key":"10.1016\/j.tcs.2026.115963_bib0031","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.orl.2005.04.003","article-title":"On the robust assignment problem under a fixed number of cost scenarios","volume":"34","author":"Deineko","year":"2006","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"10.1016\/j.tcs.2026.115963_bib0032","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2934310","article-title":"Planarizing gadgets for perfect matching do not exist","volume":"8","author":"Gurjar","year":"2016","journal-title":"ACM Trans. Comput. Theory"},{"key":"10.1016\/j.tcs.2026.115963_bib0033","series-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing","first-page":"345","article-title":"Matching is as easy as matrix inversion","author":"Mulmuley","year":"1987"},{"key":"10.1016\/j.tcs.2026.115963_bib0034","series-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"1635","article-title":"The exact bipartite matching polytope has exponential extension complexity","author":"Jia","year":"2023"},{"key":"10.1016\/j.tcs.2026.115963_bib0035","unstructured":"N.E. Maalouly, Exact matching: algorithms and related problems, (2022). arXiv: 2203.13899."},{"key":"10.1016\/j.tcs.2026.115963_bib0036","unstructured":"N.E. Maalouly, S. Haslebacher, L. Wulf, On the exact matching problem in dense graphs, (2024). arXiv: 2401.03924."},{"key":"10.1016\/j.tcs.2026.115963_bib0037","series-title":"47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)","first-page":"46:1","article-title":"Exact matching in graphs of bounded independence number","author":"Maalouly","year":"2022"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002227?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526002227?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T03:24:32Z","timestamp":1778815472000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526002227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":37,"alternative-id":["S0304397526002227"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115963","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the complexity of finding central configurations of the graph-generalized -puzzle","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115963","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115963"}}