{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T18:55:08Z","timestamp":1781463308416,"version":"3.54.1"},"reference-count":28,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T00:00:00Z","timestamp":1778112000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Japan Science and Technology Agency Strategic Basic Research Programs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2026,10]]},"DOI":"10.1016\/j.dam.2026.04.049","type":"journal-article","created":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T01:36:02Z","timestamp":1778549762000},"page":"152-175","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Reconfiguration of labeled matchings in triangular grid graphs"],"prefix":"10.1016","volume":"391","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3918-3479","authenticated-orcid":false,"given":"Naonori","family":"Kakimura","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuta","family":"Mishima","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2026.04.049_b1","series-title":"30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin\/Potsdam, Germany","first-page":"3:1","article-title":"Hardness of token swapping on trees","volume":"244","author":"Aichholzer","year":"2022"},{"key":"10.1016\/j.dam.2026.04.049_b2","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.jcss.2023.03.008","article-title":"Galactic token sliding","volume":"136","author":"Bartier","year":"2023","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.dam.2026.04.049_b3","series-title":"44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany","first-page":"80:1","article-title":"The perfect matching reconfiguration problem","volume":"138","author":"Bonamy","year":"2019"},{"issue":"9","key":"10.1016\/j.dam.2026.04.049_b4","doi-asserted-by":"crossref","first-page":"2656","DOI":"10.1007\/s00453-017-0387-0","article-title":"Complexity of token swapping and its variants","volume":"80","author":"Bonnet","year":"2018","journal-title":"Algorithmica"},{"key":"10.1016\/j.dam.2026.04.049_b5","series-title":"A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems","author":"Bousquet","year":"2022"},{"key":"10.1016\/j.dam.2026.04.049_b6","series-title":"10th International Conference on Fun with Algorithms, FUN 2021, May 30 To June 1, 2021, Favignana Island, Sicily, Italy","first-page":"7:1","article-title":"1 x 1 rush hour with fixed blocks is PSPACE-complete","volume":"157","author":"Brunner","year":"2021"},{"issue":"3","key":"10.1016\/j.dam.2026.04.049_b7","first-page":"719","article-title":"Rolling block mazes are PSPACE-complete","volume":"20","author":"Buchin","year":"2012","journal-title":"J. Inf. Process."},{"key":"10.1016\/j.dam.2026.04.049_b8","series-title":"Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings","first-page":"72","article-title":"Inapproximability of shortest paths on perfect matching polytopes","volume":"vol. 13904","author":"Cardinal","year":"2023"},{"key":"10.1016\/j.dam.2026.04.049_b9","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","article-title":"Linear-time algorithm for sliding tokens on trees","volume":"600","author":"Demaine","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2026.04.049_b10","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":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"10.1016\/j.dam.2026.04.049_b11","doi-asserted-by":"crossref","first-page":"895","DOI":"10.1016\/S0304-3975(01)00173-6","article-title":"Rush hour is PSPACE-complete, or \u201dwhy you should generously tip parking lot attendants\u201d","volume":"270","author":"Flake","year":"2002","journal-title":"Theoret. Comput. Sci."},{"issue":"24","key":"10.1016\/j.dam.2026.04.049_b12","doi-asserted-by":"crossref","first-page":"6166","DOI":"10.1016\/j.disc.2007.11.040","article-title":"Hamiltonian properties of triangular grid graphs","volume":"308","author":"Gordon","year":"2008","journal-title":"Discret. Math."},{"key":"10.1016\/j.dam.2026.04.049_b13","series-title":"31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference)","first-page":"33:1","article-title":"Gourds: A sliding-block puzzle with turning","volume":"vol. 181","author":"Hamersma","year":"2020"},{"issue":"1\u20132","key":"10.1016\/j.dam.2026.04.049_b14","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","article-title":"PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation","volume":"343","author":"Hearn","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2026.04.049_b15","series-title":"Games, Puzzles and Computation","author":"Hearn","year":"2009"},{"key":"10.1016\/j.dam.2026.04.049_b16","series-title":"Surveys in Combinatorics 2013","first-page":"127","article-title":"The complexity of change","volume":"vol. 409","author":"van\u00a0den Heuvel","year":"2013"},{"issue":"12\u201314","key":"10.1016\/j.dam.2026.04.049_b17","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito","year":"2011","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/j.dam.2026.04.049_b18","doi-asserted-by":"crossref","first-page":"1102","DOI":"10.1137\/20M1364370","article-title":"Shortest reconfiguration of perfect matchings via alternating cycles","volume":"36","author":"Ito","year":"2022","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"10.1016\/j.dam.2026.04.049_b19","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/2369492","article-title":"Notes on the \u201d15\u201d puzzle","volume":"2","author":"Johnson","year":"1879","journal-title":"Amer. J. Math."},{"key":"10.1016\/j.dam.2026.04.049_b20","series-title":"35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia","first-page":"43:1","article-title":"Reconfiguration of labeled matchings in triangular grid graphs","volume":"vol. 322","author":"Kakimura","year":"2024"},{"key":"10.1016\/j.dam.2026.04.049_b21","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.cosrev.2016.09.003","article-title":"Sorting on graphs by adjacent swaps using permutation groups","volume":"22","author":"Kim","year":"2016","journal-title":"Comput. Sci. Rev."},{"key":"10.1016\/j.dam.2026.04.049_b22","doi-asserted-by":"crossref","DOI":"10.1090\/chel\/367","article-title":"Matching theory","author":"Lov\u00e1sz","year":"2009"},{"key":"10.1016\/j.dam.2026.04.049_b23","series-title":"24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark","first-page":"66:1","article-title":"Approximation and hardness of token swapping","volume":"vol. 57","author":"Miltzow","year":"2016"},{"issue":"4","key":"10.1016\/j.dam.2026.04.049_b24","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"},{"key":"10.1016\/j.dam.2026.04.049_b25","series-title":"Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA, August 11-15, 1986. Volume 1: Science","first-page":"168","article-title":"Finding a shortest solution for the N\u00d7N extension of the 15-PUZZLE is intractable","author":"Ratner","year":"1986"},{"key":"10.1016\/j.dam.2026.04.049_b26","series-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018","first-page":"910","article-title":"The diameter of the fractional matching polytope and its hardness implications","author":"Sanit\u00e0","year":"2018"},{"key":"10.1016\/j.dam.2026.04.049_b27","series-title":"Combinatorial optimization: Polyhedra and efficiency","author":"Schrijver","year":"2003"},{"key":"10.1016\/j.dam.2026.04.049_b28","series-title":"The 15 Puzzle Book: How It Drove the World Crazy","author":"Slocum","year":"2006"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X26002775?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X26002775?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T18:08:10Z","timestamp":1781460490000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X26002775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10]]},"references-count":28,"alternative-id":["S0166218X26002775"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2026.04.049","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2026,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Reconfiguration of labeled matchings in triangular grid graphs","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2026.04.049","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}