Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Special Issue on Selected Papers from the 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022
1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
Rahnuma Islam Nishat, Venkatesh Srinivasan, and Sue Whitesides
Vol. 27, no. 4, pp. 281-327, 2023. Regular paper.
Abstract We give a complete structure theorem for $1$-complex $s,t$ Hamiltonian paths in rectangular grid graphs. We use the structure theorem to design an algorithm to reconfigure one such path into any other in linear time, making a linear number of switch operations in grid cells.
This work is licensed under the terms of the CC-BY license.
Submitted: July 2022.
Reviewed: November 2022.
Revised: February 2023.
Reviewed: April 2023.
Revised: May 2023.
Accepted: May 2023.
Final: May 2023.
Published: May 2023.