Hamiltonian Paths in Some Classes of Grid Graphs
Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri · Journal of Applied Mathematics · 2012
The Hamiltonian path problem for general grid graphs is known to be NP‐complete. In this paper, we give necessary and sufficient conditions for the existence of Hamiltonian paths in L‐alphabet, C‐alphabet, F‐alphabet, and E‐alphabet grid graphs. We also present linear‐time algorithms for finding Hamiltonian paths in these graphs.