Geodesic
Order Reconfiguration under Width Constraints
Journal of Graph Algorithms and Applications, Special Issue on Parameterized and Approximation Algorithms in Graph Drawing , Tome 27 (2023) no. 6, pp. 409-431.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this work, we consider the following order reconfiguration problem: Given a graph $G$ together with linear orders $\omega$ and $\omega'$ of the vertices of $G$, can one transform $\omega$ into $\omega'$ 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 $\omega$ and $\omega'$ have cutwidth (pathwidth) of at most $k/2$. This result also holds in a weighted setting. 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.
DOI : 10.7155/jgaa.00628
Keywords: parameterized complexity, order reconfiguration, string rewriting systems 
@article{JGAA_2023_27_6_a1,
     author = {Emmanuel Arrighi and Henning Fernau and Mateus de Oliveira Oliveira and Petra Wolf},
     title = {Order {Reconfiguration} under {Width} {Constraints}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {409--431},
     publisher = {mathdoc},
     volume = {27},
     number = {6},
     year = {2023},
     doi = {10.7155/jgaa.00628},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00628/}
}
TY  - JOUR
AU  - Emmanuel Arrighi
AU  - Henning Fernau
AU  - Mateus de Oliveira Oliveira
AU  - Petra Wolf
TI  - Order Reconfiguration under Width Constraints
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 409
EP  - 431
VL  - 27
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00628/
DO  - 10.7155/jgaa.00628
LA  - en
ID  - JGAA_2023_27_6_a1
ER  - 
%0 Journal Article
%A Emmanuel Arrighi
%A Henning Fernau
%A Mateus de Oliveira Oliveira
%A Petra Wolf
%T Order Reconfiguration under Width Constraints
%J Journal of Graph Algorithms and Applications
%D 2023
%P 409-431
%V 27
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00628/
%R 10.7155/jgaa.00628
%G en
%F JGAA_2023_27_6_a1
Emmanuel Arrighi; Henning Fernau; Mateus de Oliveira Oliveira; Petra Wolf. Order Reconfiguration under Width Constraints. Journal of Graph Algorithms and Applications, 
							Special Issue on Parameterized and Approximation Algorithms in Graph Drawing
					, Tome 27 (2023) no. 6, pp. 409-431. doi : 10.7155/jgaa.00628. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00628/

Cité par Sources :