TY - JOUR
AU - Nishat, Rahnuma Islam
AU - Srinivasan, Venkatesh
AU - Whitesides, Sue
PY - 2023/05/01
Y2 - 2024/10/05
TI - 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 27
IS - 4
SE -
DO - 10.7155/jgaa.00624
UR - https://jgaa.info/index.php/jgaa/article/view/paper624
SP - 281-327
AB - 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 <i>switch</i> operations in grid cells.
ER -