{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:40:03Z","timestamp":1727469603447},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"6","license":[{"start":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T00:00:00Z","timestamp":1688169600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>In this work, we consider the following order reconfiguration problem: \nGiven a graph $G$ together with linear orders $\\omega$ and $\\omega'$\nof the vertices of $G$, can one transform $\\omega$ into $\\omega'$ by a\nsequence of swaps of adjacent elements in such a way that, at each time step, the resulting linear\norder has cutwidth (pathwidth) at most $k$? We show that this problem \nalways has an affirmative answer when the input linear orders $\\omega$ and $\\omega'$\nhave cutwidth (pathwidth) of at most\n$k\/2$. This result also holds in a weighted setting.\nUsing this result, we establish a connection between two apparently unrelated \nproblems: the reachability problem for two-letter string rewriting systems and the graph\nisomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of \nthe famous graph isomorphism problem using techniques from term rewriting theory. <\/jats:p>","DOI":"10.7155\/jgaa.00628","type":"journal-article","created":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:42:02Z","timestamp":1689345722000},"page":"409-431","source":"Crossref","is-referenced-by-count":0,"title":["Order Reconfiguration under Width Constraints"],"prefix":"10.7155","volume":"27","author":[{"given":"Emmanuel","family":"Arrighi","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Mateus","family":"De Oliveira Oliveira","sequence":"additional","affiliation":[]},{"given":"Petra","family":"Wolf","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,7,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper628\/2324","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper628\/2324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:09:57Z","timestamp":1727467797000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,1]]},"references-count":0,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,7,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00628","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,7,1]]}}}