Journal of Applied Mathematics
Volume 2012 (2012), Article ID 475087, 17 pages
http://dx.doi.org/10.1155/2012/475087
Research Article

Hamiltonian Paths in Some Classes of Grid Graphs

Fatemeh Keshavarz-Kohjerdi1 and Alireza Bagheri2

1Department of Computer Engineering, Islamic Azad University, North Tehran Branch, Tehran, Iran
2Department of Computer Engineering and IT, Amirkabir University of Technology, Hafez Avenue, Tehran, Iran

Received 8 September 2011; Revised 13 December 2011; Accepted 28 December 2011

Academic Editor: Jin L. Kuang

Copyright © 2012 Fatemeh Keshavarz-Kohjerdi and Alireza Bagheri. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.