 |
| Home | Issues | About JGAA | Instructions for Authors |
|
Special Issue on Parameterized and Approximation Algorithms in Graph Drawing
DOI: 10.7155/jgaa.00628
Order Reconfiguration under Width Constraints
Vol. 27, no. 6, pp. 409-431, 2023. Regular paper.
Abstract 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.
 This work is licensed under the terms of the CC-BY license.
|
Submitted: March 2022.
Reviewed: December 2022.
Revised: December 2022.
Accepted: April 2023.
Final: April 2023.
Published: July 2023.
|
Journal publisher
|
Journal network
|
Journal Supporters
|
