dc.contributor.author | Arrighi, Emmanuel Jean Paul Pierre | |
dc.contributor.author | Fernau, Henning | |
dc.contributor.author | Oliveira, Mateus De Oliveira | |
dc.contributor.author | Wolf, Petra | |
dc.date.accessioned | 2022-02-17T12:47:24Z | |
dc.date.available | 2022-02-17T12:47:24Z | |
dc.date.created | 2021-09-29T16:34:22Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2979710 | |
dc.description.abstract | In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω' have cutwidth (pathwidth) at most k/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl, Leibniz-Zentrum für Informatik | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Order Reconfiguration Under Width Constraints | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.MFCS.2021.8 | |
dc.identifier.cristin | 1940799 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 8:1-8:15 | en_US |
dc.relation.project | Norges forskningsråd: 274526 | en_US |
dc.relation.project | Norges forskningsråd: 288761 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2021, 202, 8:1-8:15. | en_US |
dc.source.volume | 202 | en_US |