Hamiltonian Paths in Some Classes of Grid Graphs

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=84926
Date :  2012/02/10
Publish in :    Journal of Applied Mathematics
DOI :  https://doi.org/10.1155/2012/475087
Link :  https://www.hindawi.com/journals/jam/2012/475087/abs/
Keywords :Hamiltonian, Paths, Classes

Abstract :

---

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.